📄 the art of error correcting coding convolutional codes.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0052)http://the-art-of-ecc.com/5_Convolutional/index.html -->
<HTML><HEAD><TITLE>The Art of Error Correcting Coding: Convolutional Codes</TITLE>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="Robert Morelos-Zaragoza" name=Author>
<META
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"
name=description>
<META content="MSHTML 6.00.2900.3395" name=GENERATOR></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 simulating encoding
and decoding procedures of binary convolutional codes as well as Matlab scripts
for simulation and analysis via union bounds. Binary convolutional codes, both
nonsystematic codes and systematic (recursive) codes, and their decoding with
the Viterbi algorithm, are discussed in Chapter 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>Viterbi
decoding</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 binary
convolutional encoder. The input to the programs is a file with information of
the encoder: The number of output bits per branch, n, the memory of the encoder,
m, and the n generator polynomials in octal form. For example, to specify a
memory-2 rate-1/2 nonsystematic convolutional code (NSC) with generator
polynomials 5,7 (in hexadecimal), the <A
href="http://the-art-of-ecc.com/5_Convolutional/input_4state.data">input
file</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 contains the
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 the bit
associated with the transision and {OUT[0] OUT[1] ... OUT[n-1]} denotes the
output symbols (branch labels). <BR> </P>
<P><I>As an example, the <A
href="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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 trellis
structure of a binary convolutional encoder. Puncturing can be specified by 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 output symbols
per branch. For rate-2/3 punctued code obtained from a rate-1/2 mother code, <A
href="http://the-art-of-ecc.com/5_Convolutional/rule_23.data">the file</A> with
the puncturing rule contains 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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/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="http://the-art-of-ecc.com/5_Convolutional/bound_AWGN_R12_K3_hard.m">bound_AWGN_R12_K3_hard.m</A><BR><BR><BR>
<P><B><A href="http://the-art-of-ecc.com/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 Robert H. Morelos-Zaragoza.</FONT></SMALL></H6><!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code -->
<SCRIPT language=JavaScript
src="The Art of Error Correcting Coding Convolutional Codes.files/whv2_001.js"></SCRIPT>
<SCRIPT language=javascript>geovisit();</SCRIPT>
<NOSCRIPT><IMG height=1 alt=setstats
src="The Art of Error Correcting Coding Convolutional Codes.files/visit.gif"
width=1 border=0></NOSCRIPT></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -