15-853Algorithms in the Real World.ppt

15-853:Algorithms in the Real World Convolutional Coding Viterbi Decoding And now a word from my father… First, computer software and hardware are the most complex and rapidly developing intellectual creations of modem man. -- p. iii, Internet and Computer Law, P. B. Maggs, J. T. Soma, and J. A. Sprowl, 2001 Today’s lecture is based on A Tutorial on Convolutional Coding with Viterbi Decoding Chip Fleming Spectrum Applications /~chip.f/viterbi/tutorial.html Origin of Viterbi Decoding Andrew J. Viterbi, Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm, IEEE Transactions on Information Theory, Volume IT-13, pp. 260-269, April 1967. Viterbi is a founder of Qualcomm. Terminology k number of message symbols (as before) n number of codeword symbols (as before) r rate = k/n m number of encoding cycles an input symbol is stored K number of input symbols used by encoder to compute each output symbol (decoding time exponentially dependent on K) Convolution Encoder Encoding Example Viterbi Decoding Applications decoding trellis-coded modulation in modems most common FEC technique used in space communications (r = ?, K = 7) usually implemented as serial concatenated block and convolutional coding – first Reed-Solomon, then convolutional Turbo codes are a new parallel-concatenated convolutional coding technique State Transition and Output Tables State Transitions Trellis Oh no! Errors in received bits! Accumlated Error Metric Accumulated Error Metric Decoder Trellis Decoder Trellis Decoder Trellis Final Decoder Trellis Accumulated Error Metric over Time Surviving Predecessor States States Selected when Tracing Back Coding Gain Coding Gain Coding Gain convolutional coding with Viterbi decoding can achieve a BER of less than 1 x 10-7 at the same SNR, 6 dB k = ?, K = 3 Use 5db less power to achieve 1 x 10-7 BER than without coding Coding uses twice as much (3dB) bandwidth Coding gain: 5dB-3dB = 2dB less energy References (from Fleming) S