Coding and Error Control Review/Recap - Lecture 25

Coding and Error ControlReview/RecapLecture 25OverviewCRC AlgorithmsECCBlock ECCConvolutional CodeTurbo Codes (Block +Convolutional)ns2 Intro and installation2CRC AlgorithmQ:- List three different ways in which the CRC algorithm can be described.3Cyclic Redundancy Check (CRC)4Burst errors will most likely go undetected by a simple parity check schemeInstead, a more elaborate technique called Cyclic Redundancy Check (CRC) is typically implementedCRC appends redundant bits to the frame trailer called Frame Check Sequence (FCS)FCS is later utilized at RX for error detectionIn a given frame containing n bits, we define:k = number of original data bits(n – k) = number of bits in the FCS field (i.e. additional bits)So, that the total frame length is k + (n – k) = n bitsCRC Generation5CRC generation is all about finding the FCS given the data (D) and a divisor (P)There are three equivalent ways to generate the CRC code:Modulo-2 Arithmetic MethodPolynomial MethodDigital Logic Method6Modulo 2 ArithmeticBinary arithmetic without carryEquivalent to XOR operationi.e:0  0 = 0; 1  0 = 1; 0  1 = 1; 1  1 = 01  0 = 0; 0  1 = 0; 1  1 = 1Examples: 1010+1010___________ 0000CRC Error Detection Process7Given k-bit data (D), the TX generates an (n – k)-bit FCS field (F) such that the total n-bit frame (T) is exactly divisible by some (n-k+1)-bit predetermined devisor (P) (i.e. gives a zero remainder)In general, the received frame may or may not be equal, in value, to the sent frameLet the received frame be (T’)In error-free transmission T’ = TThe RX then divides (T’) by the same known divisor (P) and checks if there is any remainderIf division yields a remainder then the frame is erroneousIf the division yields zero remainder then the frame is error-free unless many erroneous bits in T’ resulted in a new exact division by P (This is very unlikely but possible, causing an undetected error!)CRC Generation8Data D:T = 2 (n – k)  D + FLSB? P is 1-bit longer than F(n-k) left shifts(multiplications by 2)CRC Generation9T = 2(n – k)  D + F, What is F that makes T divides P exactly ?Claim: F is the remainder obtained from dividing {2(n – k)  D} by divisor P where Q is the quotient and F is the remainderIf this is the correct F, T should now divide P with Zero remainderNote: For F to be a remainder when dividing by P, it should be 1-bit smallerCRC Generation – Modulo-2 Arithmetic MethodAt TX: CRC Generation (using previous rules):Multiply: 2(n – k)  D (left shift by (n-k) bits)Divide: 2(n – k)  D / PUse the resulting (n – k)-bit remainder as the FCSAt RX: CRC Checking: RX divides the received T (i.e. T’) by the known divisor (P) and checks if there is any remainder10Example – Modulo-2 Arithmetic MethodGivenD = 1 0 1 0 0 0 1 1 0 1P = 1 1 0 1 0 1Find the FCS fieldSolution:First we note that:The size of the data block D is k = 10 bitsThe size of P is (n – k + 1) = 6 bits  Hence the FCS length is n – k = 5  Total size of the frame T is n = 15 bits11Example – Modulo-2 Arith. Method12Solution (continued):Multiply 2(n – k)  D2(5)  1 0 1 0 0 0 1 1 0 1 = 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0This is a simple shift to the left by five positionsDivide 2(n – k)  D / P (see next slide for details)1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 ÷ 1 1 0 1 0 1 yields:Quotient Q = 1 1 0 1 0 1 0 1 1 0Remainder R = 0 1 1 1 0So, FCS = R = 0 1 1 1 0: Append it to D to get the full frame T to be transmittedT = 1 0 1 0 0 0 1 1 0 1 0 1 1 1 0 M FCS13Example – Modulo-2 Arith. Method# of bits (n-k+1) 22In addition, if all error-patterns are equally likely, and r = n - k = length of the FCS, then:For a burst error of length (r + 1), the probability of undetected error is 1/2(r – 1) For a longer burst error i.e. length > (r + 1), the probability of undetected error is 1/2 r There are four widely-used versions of P(X)CRC-12: P(X) = X12 + X11 + X3 + X2 + X + 1 (r = 13 -1 = 12)CRC-16: P(X) = X16 + X15 + X2 + 1 (r = 17 -1 = 16)CRC-CCITT: P(X) = X16 + X12 + X5 + 1CRC-32: P(X) = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1 (r = 33 -1 = 32)FCS Size23Some CRC ApplicationsCRC-8 and CRC-10 (not shown) are used in ATMCRC-12 is used for transmission of 6-bit characters. Its FCS length is 12-bitsCRC-16 & CRC-CCITT are used for 8-bit characters in the US and Europe respectivelyUsed in HDLCCRC-32 is used for IEEE 802.3 LAN standard24CRC Generation – Digital LogicData Block, D1010001101 k = 10 (size of D) (known data to be TXed) n – k + 1 = 6 size of P (known divisor) P (X) = X5+X4+X2+1 (110101) n – k = 5 size of FCS (to be determined at TX) n = 15 5-element left-shift register Initially loaded with 0’s After n left shifts, register will contain the required FCS Divisor is “hardwired” as feedback connections via XOR gates into the shift register cells Starting at LSB, for the first (n-k) bits of P, add an XOR only for 1 bitsAlwaysAn XOR at C0 P = X5+X4+X2+X0CRC Generation at TX26CRC Checking at RX27Problem 6-13A CRC is constructed to generate a 4-bit FCS for an 11-bit message. The generator polynomial is X4+X3+1Draw the shift register circuit that would perform this taskEncode the data bit sequence 10011011100 (leftmost bit is the LSB) using the generator polynomial and give the code wordNow assume that bit 7 (counting from the LSB) in the code word is in error and show that the detection algorithm detects the error28Problem 6-13 – Solution29Error CorrectionOnce an error is detected, what action can RX take? (i.e. I found an error, now what? )Two alternatives:RX asks for a retransmission of the erroneous frameAdopted by data-link protocols such as HDLC and transport protocol such as TCPA Backward Error Correction (BEC) methodRX attempts to correct the errors if enough redundancy exists in the received dataTX uses Block Coding to allow RX to correct potential errorsA Forward Error Correction (FEC) methodUse in applications that leave no time for retransmission, e.g. VoIP.30Error Correction vs. Error ControlBackward error correction by retransmission is not recommended in the following cases:Error rate is high (e.g. wireless communication)Will cause too much retransmission traffic  network overloadingTransmission distance is long (e.g. satellite, submarine optical fiber cables)Network becomes very inefficient (Not utilized properly)Usually: Error Correction methods: Those that use FEC techniquesError Control methods: Those that use retransmission31CRC AlgorithmQ:- List three different ways in which the CRC algorithm can be described.Ans:- Modulo 2 arithmetic, polynomials, and digital logic.3233ECCQ:- Is it possible to design an ECC that will correct some double bit errors but not all double bit errors? Why or why not?Ans:- It is possible. You could design a code in which all codewords are at least a distance of 3 from all other codewords, allowing all single-bit errors to be corrected. Suppose that some but not all codewords in this code are at least a distance of 5 from all other codewords. Then for those particular codewords, but not the others, a doublebit error could be corrected.3435ECCQ:- In an (n, k) block ECC, what do n and k represent?Ans:- An (n, k) block code encodes k data bits into n-bit codewords.36Convolutional CodeQ:- In an (n, k, K) convolutional code, what to n, k, and K represent?Ans:- An (n, k, K) code processes input data k bits at a time and produces an output of n bits for each incoming k bits. The current output of n bits is a function of the last K x k input bits3738What are Turbo Codes?39GoalsWhy Coding, Error Correction, etc?Basic terms and conceptsMethods of handling the noise issues40Error Control Coding/Channel CodingWhat can you do in situations where data is transmitted over a noisy channel?Adding redundancy to informationCheck codeCorrect Errors41TransmissionData is digitally recorded and compressedData is encoded by error control codingData is modulated from digital data to an analog signal42ReceptionAnalog signal is received and demodulated back to a digital signalData is processed in the Error Control DecoderRedundancy is used to check for errors and correct themData is uncompressed and presented43Transmission Process with CodingApplication LayerData CompressionChannel CodingModulationFrequency Up-conversionPower AmplificationApplication Layer Data DecompressionChannel DecodingDemodulation Frequency Down-conversionReceiverConvolutional or Turbo codingViterbi or Turbo decoding44Sensitivity to ErrorMediaSensitivity to ErrorUncompressed VoiceLow SensitivityUncompressed VideoLow SensitivityCompressed VoiceHigh SensitivityCompressed VideoHigh SensitivityDataHigh Sensitivity45Repetition CodeSimple Repetition CodeInformation Sequence {010011}Codeword {00 11 00 00 11 11}Code-rate = ½Problems with RepetitionBandwidth IncreaseDecrease the information rate46Channel CodingWhen NOT to channel code!Transmitter power is irrelevantNo noise in the channelBest case Channel CodingShannon Limit (ideal)Shannon hasn’t been reached yet (Turbo codes are the closest)47Code PerformanceBit Error Rate (BER)Probability of any particular bit being in error in a transmissionSignal to Noise Ratio (SNR)The ratio of channel power to the noise powerBest CaseLow BER (fewer errors in final data)Low SNR (less power req.)48Coding System Comparison49Error Correction CodesBlockConvolutionalTurbo codeTechnically a block code Works like both Block and Convolutional codes50Block CodeMost common is Hamming CodeTake a block of length, k (information sequence)Then encode them into a codeword, the last (n-k) bits are called parity bitsParity bits used for error checking and correcting51Block Code (2D Mapping) higher minimum weight of code, higher the minimum weight between valid code words higher weight, better decoder performance52Convolutional CodesContinuous or Streaming codingViterbi and Soft Output Viterbi are the most commonTurbo CodesMix between Convolutional and Block codesRequire a Block codeHOWEVER, they use shift registers like Convolutional Codes54Turbo Codes (contd.)Most common is the PCCC (Parallel Concatenated Convolutional Codes)Produce high weight code wordsInterleaver shuffles the input sequence, uk, in such a way that it produces a high weightTurbo Code DecoderIt requires a soft output decoderSoft-outputAssign a probability to decoded information (eg. 1 with a 80% likelihood)Outperform hard decision algorithmsMAP (Maximum A Posteriori)56Iterative Decoding57Turbo DecodingCycle will continue until certain conditions are metThe decoder circulates estimates of the sent data like a turbo engine circulates airOnce the decoder is ready, the hard decision is madeIntrinsic info (coming form the channel) and extrinsic info (that decoder adds to the intrinsic to perform its correction operation)58Error Corrections Old and New59UsesCell PhoneSatellite CommunicationDial-up CommunicationRF Communication (AutoID? WiFi?)606162What is NS2?Network SimulatorA package of tools that simulates behavior of networksCreate Network TopologiesLog events that happen under any loadAnalyze events to understand the network behavior 63ns -2 stands for Network Simulator version 2.ns -2:Is a discrete event simulator for networking researchWork at packet level.Provide substantial support to simulate bunch of protocols like TCP, UDP, FTP, HTTP and DSR.Simulate wired and wireless network.Is primarily Unix based but can also be used with Windows via Cygwin.Use TCL as its scripting language.ns -2 is a standard experiment environment in research community.What is NS2?. Cont. .Installation StepsInstallation of NS2 on Windows XPCygwinDownloading Cygwinns-allinone-2.xxDownloading NS2Installing CygwinInstalling ns-allinone-2.xx under CygwinInstallation of NS2 on Linux64INSTALLATIONWindows65INSTALLATION TIPS FORWindowGo to Website: “Requirements and Installation Tips” Carefully.66Cygwin ???Cygwin is a Linux-like environment for Windows. It consists of two parts: A DLL (cygwin1.dll) which acts as a Linux API emulation layer providing substantial Linux API functionality. A collection of tools which provide Linux look and feel. The Cygwin DLL currently works with all recent, commercially released x86 32 bit and 64 bit versions of Windows, with the exception of Windows CE67DOWNLOADING CygwinDownload cygwin from: Run setup.exe any time you want to update or install a Cygwin package.Note that, when installing packages for the first time, setup.exe does not install every package. Only the minimal base packages from the Cygwin distribution are installed by default. 68RUN SETUP69INSTALLER70CYGWIN SOURCES71SET SOURCE (Internet)72SET DESTINATION73SELECT PACKAGES74LOCAL PACKAGE DIRECTORY75SELECT MIRRORS76INSTALLATION PROGRESS77SET SOURCE (local directory)78SET DESTINATION79REACH TO “INI” FILE80SELECT PACKAGES81INSTALLATION STARTED82INSTALLATION COMPLETE83ICON ON THE DESKTOPRun Cygwin Shell(Generate Home directory)84DOWNLOADING ns-allinone-2.xxDownload ns-allinone-2.xx.tar.gz from: Current version is available at sourceforge.net 85INSTALL NS-2 IN CYGWIN Extract and Copy the folder “ns-allinone-2.30” in C:\cygwin\home\Administrator Enter into “ns-allinone-2.30” folder through terminal: cd ns-allinone-2.30\ Enter ./install command in cygwin terminal86Installation87Installation88Installation89Installation90Replace COMMA with COLON&There should be NO SPACESInstallation9192InstallationInstallation93Installation94X SERVER95HOW TO RUN .tcl FILECommand:ns filename.tcl96INSTALLATIONIN LINUX (FEDORA-CORE 4)97EXTRACT THE .gz ARCHIVE98CUT THE FOLDER99PASTE TO HOME FOLDER100LAUNCH TERMINAL CLIENT101GOTO NS-ALLINONE FOLDER102RUN INSTALL103END OF INSTALL SCRIPT104SHOW HIDDEN FILES105LOCATE .bashrc106FOLLOW THE INSTRUCTIONS107ADD TO PATH108ADD LIBRARY_PATHS109RUN validate110INSTALLATION VALIDATED111SummaryCRC AlgorithmsECCBlock ECCConvolutional CodeTurbo Codes (Block +Convolutional)ns2 Intro and installation112113