📄 index2.htm
字号:
<!DOCTYPE html PUBLIC "-//w3c//dtd html 4.0 transitional//en"><html><head> <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> <meta name="Author" content="Robert Morelos-Zaragoza"> <meta name="description" content="Error Control Coding,Error CorrectingCoding,Error Correcting Codes,FEC,Turbo Codes,Iterative Decoding,DigitalCommunications,Wireless,Satellite,Data,Coded Modulation,Golay,Hamming,BCH,Reed Solomon,Viterbi Decoder,Soft Decision Decoding,Sudan Algorithm,Unequal Error Protection,Variable Rate Coding,Adaptive Coding,Convolutional Codes,LDPC,Low-Density Parity-Check Codes,The Art of Error-Correcting Coding,Capacity-achieving codes,Coding is not dead, is more alive than ever"><title>The Art of Error Correcting Coding: Convolutional Codes</title></head><body bgcolor="#ffffff"><center><b><font size="+1">Convolutional Codes and the Viterbi Algorithm</font></b></center><p>This page contains pointers to several programs in C for simulatingencoding and decoding procedures of binary convolutional codes as wellas Matlab scripts for simulation and analysis via union bounds. Binaryconvolutional codes, both nonsystematic codes and systematic(recursive)codes, and their decoding with the Viterbi algorithm, are discussed inChapter 5 of the <a href="http://www.amazon.com/gp/product/0470015586/ref=sr_11_1/102-3025380-7157754?ie=UTF8">book</a>.</p><p>In simulating of a given convolutional codes, there are two steps: (1)Setting up a file with the <b><i>trellis structure</i></b> and (2) <b><i>Viterbidecoding</i></b> using this structure.<br> </p><p><big><b>1. Trellis structure</b></big></p><p><i>The two C programs below generate the trellis structure of a binaryconvolutional encoder. The input to the programs is a file with informationof the encoder: The number of output bits per branch, n, the memory ofthe encoder, m, and the n generator polynomials in octal form. For example,to specify a memory-2 rate-1/2 nonsystematic convolutional code (NSC) withgenerator polynomials 5,7 (in hexadecimal), the <a href="input_4state.data">inputfile</a> contains the lines:</i></p><p><i>2 2</i><br><i>5</i><br><i>7</i></p><p><i>The trellis structure is written to an output file that containsthe following information, where k=1 in the current versions:</i><font size="-2"></font></p><p><i>n m</i><br><i>2^m n 2^k</i><br><i>g1</i><br><i>g2</i><br><i>... gn</i><br><i>INIT DATA FINAL OUT[0] OUT[1] ... OUT[n-1]</i><br><i>INIT DATA FINAL OUT[0] OUT[1] ... OUT[n-1]</i><br><i>...</i><br><i>INIT DATA FINAL OUT[0] OUT[1] ... OUT[n-1]</i></p><p>where INIT and FINAL denote the initial and final states, DATA is thebit associated with the transision and {OUT[0] OUT[1] ... OUT[n-1]} denotesthe output symbols (branch labels).<br> </p><p><i>As an example, the <a href="trellis_4states.data">output file</a>for the memory-2 rate-1/2 NSC contains the lines:</i></p><p><i>2 2</i><br><i>4 2 2</i><br><i>5</i><br><i>7</i><br><i> 0 0 0 1 1</i><br><i> 0 1 1 -1 -1</i><br><i> 1 0 2 1 -1</i><br><i> 1 1 3 -1 1</i><br><i> 2 0 0 -1 -1</i><br><i> 2 1 1 1 1</i><br><i> 3 0 2 -1 1</i><br><i> 3 1 3 1 -1</i></p><p><i>The same comments hold for nonrecursive systematic encoders.</i><br> </p><p><b>Generate trellis data of a memory-m rate-1/n convolutional encoder:Nonsystematic case</b><br><a href="generate_trellis_nsc.c">generate_trellis_nsc.c</a><br> </p><p><b>Generate trellis data of a memory-m rate-1/n convolutional encoder:Recursive systematic case</b><br><a href="generate_trellis_rsc.c">generate_trellis_rsc.c</a><br> </p><p><big><b>2. Viterbi decoding and puncturing rules</b></big></p><p><i>The programs below implement the VD algorithm operating on the trellisstructure of a binary convolutional encoder. Puncturing can be specifiedby a rule, which is input to the program via a file containing the lines</i><br><i>PERIOD</i><br><i>bit(1,1) bit(1,2) ... bit(1,PERIOD)</i><br><i>...</i><br><i>bit(n,1) bit(n,2) ... bit(n,PERIOD)</i></p><p><i>where PERIOD is the puncturing period and n the number of outputsymbols per branch. For rate-2/3 punctued code obtained from a rate-1/2mother code, <a href="rule_23.data">the file</a> with the puncturing rulecontains the lines:</i><br><i>2</i><br><i>1 0</i><br><i>1 1</i><br> </p><p><b>Viterbi decoder, hard-decision decoding, BSC with Hamming metric:NSC</b><br><a href="viterbi_binary_hard.c">viterbi_binary_hard.c</a><br></p><p><b>Viterbi decoder, AWGN channel with correlation metric: NSC</b><br><a href="viterbi_binary_nsc.c">viterbi_binary_nsc.c</a><br></p><p><b>Viterbi decoder, AWGN channel with correlation metric: RSC</b><br><a href="viterbi_binary_rsc.c">viterbi_binary_rsc.c</a><br></p><p><b>Viterbi decoder, AWGN channel with correlation metric: NSC with puncturing</b><br><a href="viterbi_binary_punct.c">viterbi_binary_punct.c</a><br> <br></p><span style="font-weight: bold;">Bounds on the performance of two binary rate-1/2 convolyutional codes over a BSC:</span><br><a href="bound_BSC_R12_K3_K4_hard.m">bound_BSC_R12_K3_K4_hard.m</a><br><br><br style="font-weight: bold;"><span style="font-weight: bold;">VO and JZ bounds on performance of a memory-1 rate-1/2 convolutional code over an AWGN channel:</span><br><a href="bound_AWGN_R12_K2_EbNo.m">bound_AWGN_R12_K2_EbNo.m</a><br><br><span style="font-weight: bold;">Simulation of a memory-1 rate-1/2 convolutional code over an AWGN channel:</span><br><a href="AWGN_conv_R12_K2.m">AWGN_conv_R12_K2.m</a><br><br style="font-weight: bold;"><span style="font-weight: bold;">VO and JZ bounds on performance of a memory-2 rate-1/3 convolutional code over an AWGN channel:</span><br><a href="bound_AWGN_R13_K3_EbNo.m">bound_AWGN_R13_K3_EbNo.m</a><br><br><span style="font-weight: bold;">Simulation of a memory-2 rate-1/3 convolutional code over an AWGN channel:</span><br><a href="AWGN_conv_R13_K3.m">AWGN_conv_R13_K3.m</a><br><br><span style="font-weight: bold;">Viterbi decoding of a memory-2 rate-1/2 convolutional code over an AWGN channel - Hard decisions:</span><br><a href="AWGN_conv_R12_K3_hard.m">AWGN_conv_R12_K3_hard.m</a><br><br><span style="font-weight: bold;">Viterbi decoding of a memory-2 rate-1/2 convolutional code over an AWGN channel - Soft decisions:</span><br><a href="AWGN_conv_R12_K3.m">AWGN_conv_R12_K3.m</a><br><br><span style="font-weight: bold;">Bound on the performance of a memory-2 rate-1/2 convolutional code over an AWGN channel with soft-decision decoding:</span><br><a href="bound_AWGN_R12_K3.m">bound_AWGN_R12_K3.m</a><br><br><span style="font-weight: bold;">Bound on the performance of a memory-2 rate-1/2 convolutional code over an AWGN channel with hard-decision decoding:</span><br><a href="bound_AWGN_R12_K3_hard.m">bound_AWGN_R12_K3_hard.m</a><br><br><br><p><b><a href="../topics.html">BACK TO CONTENTS</a></b><br></p><hr><h6 style="font-weight: normal;"><small><font color="#000000">This page was last updated on August 6, 2008, by RobertH. Morelos-Zaragoza.</font></small></h6></body></html><!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://us.js2.yimg.com/us.js.yimg.com/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1223490624" alt="setstats" border="0" width="1" height="1"></noscript>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -