COM 5140 Error-Correcting Codes
Spring 2024
Project No. 1
Due 4:00pm, May 16, 2024
You are expected to produce a program to implement the Viterbi decoding algorithm for
the widely used (2, 1, 6) convolutional code with generator matrix
G(D) = (1 + D
2 + D
3 + D
5 + D
6
1 + D + D
2 + D
3 + D
6
).
This code is assumed to be transmitted over an additive white Gaussian noise (AWGN)
channel.
The deliverable will consist of three parts:
? Part I, Demonstration. At the time of demonstration, we will let you know: the
number of decoded bits N, the bit signal-to-noise ratio (SNR) Eb/N0 (in dB), the seed
for the random number generator, and hard or (unquantized) soft decision. You should
then report in each case the number of decoded bit errors made by your decoder and
the corresponding bit error rate (BER). I want you to truncate your survivors at length
32, outputting the oldest bit on the survivor with the best metric.
? Part II, Report. You should run experiments with your Viterbi decoder to produce
performance curves showing the relationships between Eb/N0 (in dB) and the decoded
BER (in logarithmic scale), with both hard-decision decoding, which corresponds to
decoding on a binary symmetric channel (BSC), and unquantized soft-decision decod?ing, for Eb/N0 ranging from 1 dB to 6 dB for hard decision and 1 dB to 4 dB for
unquantized soft decision, with increments of 0.5 dB. Please also include your simula?tion data in tabular form, listing for each data point: the bit SNR E0/N0, the number
of decoded bits, the number of decoded bit errors, and the BER. (These detailed data
are only required for the two mandatory performance curves.) Please hand in before
the deadline a report (in a hard copy) which includes, among other things, performance
curves, and (optional) discussions of issues like output decision alternatives (best-state,
fixed-state, majority-vote), survivor truncation length, etc. Your computer program
with comments should be attached at the end of the report.
? Part III, Program file. You also need to submit, before the deadline, your program
file. Please put all of your programs into a single file with your registration number and
proj1 as the file name, say, 105064851 proj1.c or 105064851 proj1.cpp. (If, after all
kinds of attempts, you are still unable to put all of your programs in a single file, please
compress your files into a single rar or zip file and use your registration number along
with proj1 as the file name, say, 105064851 proj1.rar or 105064851 porj1.zip.)
Upload your file to the eeclass system.
Additional Details on Project No. 1
1. Use the recursion
ul+6 = ul+1 ul
, for l 0
with the initial conditions u0 = 1, u1 = u2 = u3 = u4 = u5 = 0 to generate the infor?mation bits. Ensure that the generated sequence is 100000100001 . . . and is periodic
with period 63.
2. Encode the information sequence using the generator matrix G(D).
3. The encoder outputs 0 s and 1 s. However, the input to the AWGN channel is normal?ized to 1. Therefore, map 0 s to +1 s and 1 s to ?1 s.
4. To simulate the AWGN channel with unquantized soft-decision decoding, add a normal
(Gaussian) random variable of mean zero and variance
2
to the 1 s generated at the
previous step. For a binary code of rate R on the AWGN channel with antipodal
signaling, the relationship between Eb/N0 and
2
is given by
2 =
2R
Eb
N0
?1
so for example for a R = 1/2 code, the relationship is simply
2 =
Eb
N0
?1
.
Please remember that Eb/N0 is always quoted in dBs, which equals 10 log10(Eb/N0).
Thus for example, a value of Eb/N0 of 4 dB for a R = 1/2 code corresponds to a value
of
2 = 0.3981.
5. Use the following segment of pseudo code to generate normal random variables of
mean zero and variance
2
. The procedure normal outputs two independent normal
random variables, n1 and n2, and Ranq1 is a function which generates a random variable
uniformly distributed in the interval (0, 1).
unsigned long long SEED;
// SEED must be an unsigned integer smaller than 4101842887655102017.
unsigned long long RANV;
int RANI = 0;
main()
{
}
2
normal(n1, n2, )
{
do{
x1 = Ranq1();
x2 = Ranq1();
x1 = 2x1 ? 1;
x2 = 2x2 ? 1;
s = x
2
1 + x
2
2;
} while (s 1.0)
n1 = x1
q ?2 ln s/s;
n2 = x2
q ?2 ln s/s;
}
double Ranq1()
{
if ( RANI == 0 ){
RANV = SEED 4101842887655102017LL;
RANV = RANV >> 21;
RANV = RANV << 35;
RANV = RANV >> 4;
RANV = RANV * 2685821657736338717LL;
RANI++;
}
RANV = RANV >> 21;
RANV = RANV << 35;
RANV = RANV >> 4;
return RANV * 2685821657736338717LL * 5.42101086242752217E-20;
}
6. To get the output of the BSC, take the sign of the output of the AWGN channel and
map +1 s to 0 s and ?1 s to 1 s.
7. In your decoder, truncate the survivors to length 32 and output the oldest bit on the
survivor with the best metric. To decode N bits, generate N + 31 bits in (1). Finally
compare the decoded information sequence with the original information sequence. If
there are K bit errors, K/N will be a good estimate of the decoded BER.
8. As a partial check, some typical values are listed below.
Eb/N0 BER (BSC) Eb/N0 BER (AWGN)
4.5 dB 2.1 10?3 2.5 dB 2.2 10?3
5.0 dB 6.4 10?4 3.0 dB 5.3 10?4
3
Other Notes for Demonstration
1. The survivor truncation length corresponds to the actual storage requirement of the
survivors. For example, a survivor truncation length of 32 for this code means that
each survivor stores 32 bits.
2. For the illustration below, suppose a state is described as the content of the feed-forward
shift register in the encoder s = (s1, s2, s3, s4, s5, s6), where the input information bit
first fed to s1 and then shifted from left to right. In the trellis diagram, consider placing
the states vertically from top to bottom in the order of (0 0 0 0 0 0), (1 0 0 0 0 0),
(0 1 0 0 0 0), (1 1 0 0 0 0), (0 0 1 0 0 0), . . ., (1 1 1 1 1 1). What to do in case of tied
metrics? In the add-compare-select step the two metrics could be equal. In this case,
if 0 s and 1 s are equally probable to occur in the transmitted information sequence, in
principle you can safely select either case, and it will not affect the decoder performance.
Yet for the purpose of demonstration, always choose the upper branch as the survivor.
If best-state output decision is employed, in case of tied metrics, in principle you can
also safely select either case, but again for the purpose of demonstration, always choose
the survivor of the uppermost state.
3. Except in the procedure normal for generating noise, if a random number is needed in
your program, use other random number generators instead of the function Ranq1, for
the purpose of demonstration.
4. Each call of the procedure normal can return two independent normal random vari?ables, n1 and n2. Please use both of them in your program. Specifically, since this is
a (2, 1) code, each branch transition consists of two encoded bits, say x1 and x2. Add
n1 and n2 to x1 and x2, respectively, to get the two channel outputs y1 and y2, i.e.,
y1 = x1 + n1 and y2 = x2 + n2.
请加QQ：99515681 邮箱：99515681@qq.com WX：codinghelp