Intro to coding and convolutional codes802.11a Convolutional EncoderWhat we’ll cover todayChannel codingSequential encoderExamplesExample: Binary PAM differential encoderThe TrellisExample sequences for differential encoderA simple convolutional codeTrellis for convolutional code exampleDistance between sequencesHamming distanceEuclidean distanceTrellis codes – Euclidean distance exampleChannel as encoderGenerator and Parity matricesConstraint length ( )Example, repeated8-state Ungerboeck encoder exampleTrellis diagram for 8-state code8-state Ungerboeck code with feedbackImplementations/Systematic encodersCatastrophic encoderCoding gain – comparisonCoding gain – comparisonCodes from tablesReadings6.973 Communication System Design – Spring 2006Massachusetts Institute of TechnologyLecture 11Vladimir StojanovićCite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].Intro to coding and convolutional codes802.11a Convolutional Encoder Rate 1/2 convolutional encoder Punctured to obtain 2/3 and 3/4 rate Omit some of the coded bits 64-state (constraint length K=7) code Viterbi algorithm applied in the decoderCite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].6.973 Communication System Design2Output data AOutput data BInput dataTbTbTbTbTbTbX0X1X2X3X4X5X6X7X8y0 y1 y2 y3 y4 y5 y6 y7 y8A0B0A1B2A3B3A4B5A6A7B8B6A0A1A2A3A4A5A6A7A8B0B1B2B3B4B5B6B7B8Punctured coding (r = 3/4)Source dataEncoded dataBit stolen data(sent/received data)Stolen bitA0A1A2A3A4A5A6A7A8B0B1B2B3B4B5B6B7B8Bit inserted dataDecoded dataInserted dummybitg1 = 1718g0 = 1338Figure by MIT OpenCourseWare.What we’ll cover today What are convolutional codes? How they help How to encode/decode themCite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].6.973 Communication System Design36.973 Communication System Design4Channel coding To enhance robustness, tie bits into sequences, then decide on sequences rather than individual received bits Encoder Memory-less: translates incoming message mkat time k into a symbol vector xk(modulator later converts xkto xk(t)) Sequential: map message bits into larger dimensionality symbols that can also depend on previous message bits through the state of the encoder Codewords Finite (block code) Semi-Infinite (tree/convolutional code) Example Block code - Majority repetition binary code (0->-1-1-1, 1->+1+1+1) ML decoder computes the majority polarity for the received signal 1/3 bits per symbol with min.distance 2*sqrt(3) Tree code – Transmit -1-1-1 if the bit has not changed, transmit +1+1+1 otherwiseCite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].codecodewordSequential encoder bits determine “state” skat time k There are states Encoding of bits into symbols can vary with encoder state For each state encoder accepts b bits of input (mk) and outputs a corresponding N-dimensional output vector (this is repeated once every symbol period T) Data rate of the encoder is Block code if there is only one state (tree code otherwise)ν2νCite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].6.973 Communication System Design5Image removed due to copyright restrictions.6.973 Communication System Design6Examples QAM is a block code There is only one state in QAM Let 1/T=2.4kHz and For 4 QAM, R=2/T=2*2400=4800bps, bit/dimension For 16 QAM, R=4/T=9600bps, For 256 QAM, R=8/T=19200bps, 0ν=2/2 1b==4/2 2b==8/2 4b ==Cite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].Example: Binary PAM differential encoderν= 1 2-states (corresponding to the possible values of the previous single-bit message) Example of a sequential encoder with Differential encoder encodes the difference modulo-M between successive message inputs to the sequential encoder In binary case it only transmits a 1 on a change of a bit in a message Cite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].6.973 Communication System Design7The Trellis Describes the progression of symbols within a code Example – binary PAM differential encoder trellis Two states in each time corresponding to the value of previouslytransmitted message Time-invariant encoder only requires trellis representation at k and k+1 A trellis branch connects two states and corresponds to a possible input (always 2bbranches emanating from any state) Each branch labeled with a channel symbol and corresponding input xk/mkCite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts Institute of Technology. Downloaded on [DD Month YYYY].6.973 Communication System Design8 Semi-infinite series of branches starting from a known state To determine dmin of a code, need only find the two sequences through the trellis that have minimum separation Would be the same for long period before and after the short period of divergence For example, min distance between a sequence of no-changes and a single bit change would be d2min=4=(+1-(-1))2 No gain when compared to uncoded PAM2, but that is o.k. in this case since differential encoder’s purpose is to make the decoder insensitive to a sign ambiguity in transmissionCite as: Vladimir Stojanovic, course materials for 6.973 Communication System Design, Spring 2006.MIT OpenCourseWare (http://ocw.mit.edu/), Massachusetts
View Full Document