11.12   A Viterbi Decoder

Chapter start

Previous page

Next page

# 11.12   A Viterbi Decoder

This section describes an ASIC design for a Viterbi decoder using Verilog. Christeen Gray completed the original design as her MS thesis at the University of Hawaii (UH) working with VLSI Technology, using the Compass ASIC Synthesizer and a VLSI Technology cell library. The design was mapped from VLSI Technology design rules to Hewlett-Packard design rules; prototypes were fabricated by Hewlett-Packard (through Mosis) and tested at UH.

## 11.12.1   Viterbi Encoder

Viterbi encoding is widely used for satellite and other noisy communications channels. There are two important components of a channel using Viterbi encoding: the Viterbi encoder (at the transmitter) and the Viterbi decoder (at the receiver). A Viterbi encoder includes extra information in the transmitted signal to reduce the probability of errors in the received signal that may be corrupted by noise.

I shall describe an encoder in which every two bits of a data stream are encoded into three bits for transmission. The ratio of input to output information in an encoder is the rate of the encoder; this is a rate 2/3 encoder. The following equations relate the three encoder output bits (Yn2 , Yn1 , and Yn0 ) to the two encoder input bits (Xn2 and Xn1 ) at a time nT:

Yn2 = Xn2

Yn1 = Xn1 xor Xn-21

Yn0 = Xn-11

We can write the input bits as a single number. Thus, for example, if Xn2 = 1 and Xn2 = 0 , we can write Xn = 2 . Equation 11.1 defines a state machine with two memory elements for the two last input values for Xn1 : Xn-11 and Xn-21 . These two state variables define four states: {Xn-11, Xn-21 } , with S0 = { 0, 0}, S1 = {1, 0}, S2 = {0, 1}, and S3 = {1, 1}. The 3-bit output Yn is a function of the state and current 2-bit input Xn .

The following Verilog code describes the rate 2/3 encoder. This model uses two D flip-flops as the state register. When reset (using active-high input signal `res` ) the encoder starts in state S0 . In Verilog I represent Yn2 by `Y2N` , for example.

```/******************************************************/
/* module viterbi_encode                              */
/******************************************************/
/* This is the encoder. X2N (msb) and X1N form the 2-bit input
message, XN. Example: if X2N=1, X1N=0, then XN=2. Y2N (msb), Y1N, and
Y0N form the 3-bit encoded signal, YN (for a total constellation of 8
PSK signals that will be transmitted). The encoder uses a state
machine with four states to generate the 3-bit output, YN, from the
2-bit input, XN. Example: the repeated input sequence XN = (X2N, X1N)
= 0, 1, 2, 3 produces the repeated output sequence YN = (Y2N, Y1N,
Y0N) = 1, 0, 5, 4. */
module viterbi_encode(X2N,X1N,Y2N,Y1N,Y0N,clk,res);
input X2N,X1N,clk,res; output Y2N,Y1N,Y0N;
wire X1N_1,X1N_2,Y2N,Y1N,Y0N;
dff dff_1(X1N,X1N_1,clk,res); dff dff_2(X1N_1,X1N_2,clk,res);
assign Y2N=X2N; assign Y1N=X1N ^ X1N_2; assign Y0N=X1N_1;
endmodule ```

Figure 11.3 shows the state diagram for this encoder. The first four rows of Table 11.6 show the four different transitions that can be made from state S0 . For example, if we reset the encoder and the input is Xn = 3 (Xn2 = 1 and Xn1 = 1), then the output will be Yn = 6  (Yn2 = 1 ,  Yn1 = 1 , Yn0 = 0 ) and the next state will be S1 .

 FIGURE 11.3  A state diagram for a rate 2/3 Viterbi encoder. The inputs and outputs are shown in binary as Xn2 Xn1 / Yn2Yn1Yn0 , and in decimal as Xn/ Yn .
 TABLE 11.6    State table for the rate 2/3 Viterbi encoder. Present state Outputs Inputs State variables Yn2 Yn1 Yn0 Next state Xn2 Xn1 Xn-11 Xn-21 Xn2 = Xn1 xor Xn-21 = Xn-11 {Xn-11, Xn-21} S0 0 0 0 0 0 0 0 00 S0 S0 0 1 0 0 0 1 0 10 S1 S0 1 0 0 0 1 0 0 00 S0 S0 1 1 0 0 1 1 0 10 S1 S1 0 0 1 0 0 0 1 01 S2 S1 0 1 1 0 0 1 1 11 S3 S1 1 0 1 0 1 0 1 01 S2 S1 1 1 1 0 1 1 1 11 S3 S2 0 0 0 1 0 1 0 00 S0 S2 0 1 0 1 0 0 0 10 S1 S2 1 0 0 1 1 1 0 00 S0 S2 1 1 0 1 1 0 0 10 S1 S3 0 0 1 1 0 1 1 01 S2 S3 0 1 1 1 0 0 1 11 S3 S3 1 0 1 1 1 1 1 01 S2 S3 1 1 1 1 1 0 1 11 S3

As an example, the repeated encoder input sequence Xn = 0, 1, 2, 3, ... produces the encoder output sequence Yn = 1, 0, 5, 4, ... repeated. Table 11.7 shows the state transitions for this sequence, including the initialization steps.

 FIGURE 11.4  The signal constellation for an 8 PSK (phase-shift keyed) code.
 TABLE 11.7    A sequence of transmitted signals for the rate 2/3 Viterbi encoder Time ns Inputs State variables Outputs Present state Next state Xn2 Xn1 Xn-11 Xn-21 Yn2 Yn1 Yn0 0 1 1 x x 1 x x S? S? 10 1 1 0 0 1 1 0 S0 S1 50 0 0 1 0 0 0 1 S1 S2 150 0 1 0 1 0 0 0 S2 S1 250 1 0 1 0 1 0 1 S1 S2 350 1 1 0 1 1 0 0 S2 S1 450 0 0 1 0 0 0 1 S1 S2 550 0 1 0 1 0 0 0 S2 S1 650 1 0 1 0 1 0 1 S1 S2 750 1 1 0 1 1 0 0 S2 S1 850 0 0 1 0 0 0 1 S1 S2 950 0 1 0 1 0 0 0 S2 S1

Next we transmit the eight possible encoder outputs (Yn = 0-7 ) as signals over our noisy communications channel (perhaps a microwave signal to a satellite) using the signal constellation shown in Figure 11.4. Typically this is done using phase-shift keying ( PSK) with each signal position corresponding to a different phase shift in the transmitted carrier signal.

The noisy signal enters the receiver. It is now our task to discover which of the eight possible signals were transmitted at each time step. First we calculate the distance of each received signal from each of the known eight positions in the signal constellation. Table 11.8 shows the distances between signals in the 8PSK constellation. We are going to assume that there is no noise in the channel to illustrate the operation of the Viterbi decoder, so that the distances in Table 11.8 represent the possible distance measures of our received signal from the 8PSK signals.

The distances, X, in the first column of Table 11.8 are the geometric or algebraic distances. We measure the Euclidean distance, E = X2 shown as B (the binary quantized value of E) in Table 11.8. The rounding errors that result from conversion to fixed-width binary are quantization errors and are important in any practical implementation of the Viterbi decoder. The effect of the quantization error is to add a form of noise to the received signal.

The following code models the receiver section that digitizes the noisy analog received signal and computes the binary distance measures. Eight binary-distance measures, `in0-in7` , are generated each time a signal is received. Since each of the distance measures is 3 bits wide, there are a total of 24 bits (8 ¥ 3) that form the digital inputs to the Viterbi decoder.

 TABLE 11.8    Distance measures for Viterbi encoding (8PSK). Signal Algebraic distance from signal 0 X = Distance from signal 0 Euclidean distance E = X2 B = binary quantized value of E D = decimal value of B Quantization error Q = D - 1.75 E 0 2 sin (0 π / 8) 0.00 0.00 000 0 0 1 2 sin (1 π / 8) 0.77 0.59 001 1 -0.0325 2 2 sin (2 π / 8) 1.41 2.00 100 4 0.5 3 2 sin (3 π / 8) 1.85 3.41 110 6 0.0325 4 2 sin (4 π / 8) 2.00 4.00 111 7 0 5 2 sin (5 π / 8) 1.85 3.41 110 6 0.0325 6 2 sin (6 π / 8) 1.41 2.00 100 4 0.5 7 2 sin (7 π / 8) 0.77 0.59 001 1 -0.0325

```/******************************************************/
/* module viterbi_distances                           */
/******************************************************/
/* This module simulates the front end of a receiver. Normally the
received analog signal (with noise) is converted into a series of
distance measures from the known eight possible transmitted PSK
signals: s0,...,s7. We are not simulating the analog part or noise in
this version, so we just take the digitally encoded 3-bit signal, Y,
from the encoder and convert it directly to the distance measures.
d[N] is the distance from signal = N to signal = 0
d[N] = (2*sin(N*PI/8))**2 in 3-bit binary (on the scale 2=100)
Example: d[3] = 1.85**2 = 3.41 = 110
inN is the distance from signal = N to encoder signal.
Example: in3 is the distance from signal = 3 to encoder signal.
d[N] is the distance from signal = N to encoder signal = 0.
If encoder signal = J, shift the distances by 8-J positions.
Example: if signal = 2, in0 is d[6], in1 is D[7], in2 is D[0], etc. */
module viterbi_distances
(Y2N,Y1N,Y0N,clk,res,in0,in1,in2,in3,in4,in5,in6,in7);
input clk,res,Y2N,Y1N,Y0N; output in0,in1,in2,in3,in4,in5,in6,in7;
reg [2:0] J,in0,in1,in2,in3,in4,in5,in6,in7; reg [2:0] d [7:0];
initial begin d[0]='b000;d[1]='b001;d[2]='b100;d[3]='b110;
d[4]='b111;d[5]='b110;d[6]='b100;d[7]='b001; end
always @(Y2N or Y1N or Y0N) begin
J[0]=Y0N;J[1]=Y1N;J[2]=Y2N;
J=8-J;in0=d[J];J=J+1;in1=d[J];J=J+1;in2=d[J];J=J+1;in3=d[J];
J=J+1;in4=d[J];J=J+1;in5=d[J];J=J+1;in6=d[J];J=J+1;in7=d[J];
end endmodule```

As an example, Table 11.9 shows the distance measures for the transmitted encoder output sequence Yn = 1, 0, 5, 4, ... (repeated) corresponding to an encoder input of Xn = 0, 1, 2, 3, ... (repeated).

 TABLE 11.9    Receiver distance measures for an example transmission sequence. Time ns Input Xn Output Yn Present state Next state in0 in1 in2 in3 in4 in5 in6 in7 0 3 x S? S? x x x x x x x x 10 3 6 S0 S1 4 6 7 6 4 1 0 1 50 0 1 S1 S2 1 0 1 4 6 7 6 4 150 1 0 S2 S1 0 1 4 6 7 6 4 1 250 2 5 S1 S2 6 7 6 4 1 0 1 4 350 3 4 S2 S1 7 6 4 1 0 1 4 6 450 0 1 S1 S2 1 0 1 4 6 7 6 4 550 1 0 S2 S1 0 1 4 6 7 6 4 1 650 2 5 S1 S2 6 7 6 4 1 0 1 4 750 3 4 S2 S1 7 6 4 1 0 1 4 6 850 0 1 S1 S2 1 0 1 4 6 7 6 4 950 1 0 S2 S1 0 1 4 6 7 6 4 1

## 11.12.3   Testing the System

Here is a testbench for the entire system: encoder, receiver front end, and decoder:

```/*****************************************************/
/* module viterbi_test_CDD                           */
/*****************************************************/
/* This is the top-level module, viterbi_test_CDD, that models the
communications link. It contains three modules: viterbi_encode,
viterbi_distances, and viterbi. There is no analog and no noise in
this version. The 2-bit message, X, is encoded to a 3-bit signal, Y.
In this module the message X is generated using a simple counter.
The digital 3-bit signal Y is transmitted, received with noise as an
analog signal (not modeled here), and converted to a set of eight
3-bit distance measures, in0, ..., in7. The distance measures form
the input to the Viterbi decoder that reconstructs the transmitted
signal Y, with an error signal if the measures are inconsistent.
CDD = counter input, digital transmission, digital reception */
module viterbi_test_CDD;
wire Error;        // decoder out
wire [2:0] Y, Out; // encoder out, decoder out
reg [1:0] X;       // encoder inputs
reg Clk, Res;      // clock and reset
wire [2:0] in0,in1,in2,in3,in4,in5,in6,in7;
always #500 ("t    Clk X Y Out Error");
initial ("%4g",,,Clk,,,,X,,Y,,Out,,,,Error);
initial ; initial #3000 ;
always #50 Clk = ~Clk; initial begin Clk = 0;
X = 3; // No special reason to start at 3.
#60 Res = 1;#10 Res = 0; end // Hit reset after inputs are stable.
always @(posedge Clk) #1 X = X + 1; // Drive the input with a counter.
viterbi_encode v_1
(X[1],X[0],Y[2],Y[1],Y[0],Clk,Res);
viterbi_distances v_2
(Y[2],Y[1],Y[0],Clk,Res,in0,in1,in2,in3,in4,in5,in6,in7);
viterbi v_3
(in0,in1,in2,in3,in4,in5,in6,in7,Out,Clk,Res,Error);
endmodule```

The Viterbi decoder takes the distance measures and calculates the most likely transmitted signal. It does this by keeping a running history of the previously received signals in a path memory. The path-memory length of this decoder is 12. By keeping a history of possible sequences and using the knowledge that the signals were generated by a state machine, it is possible to select the most likely sequences.

TABLE 11.10    Output from the Viterbi testbench

```t    Clk X Y Out Error
0  0   3 x x   0
50  1   3 x x   0
51  1   0 x x   0
60  1   0 0 0   0
100  0   0 0 0   0
150  1   0 0 0   0
151  1   1 2 0   0```
```t    Clk X Y Out Error
1351 1   1 0 0   0
1400 0   1 0 0   0
1450 1   1 0 0   0
1451 1   2 5 2   0
1500 0   2 5 2   0
1550 1   2 5 2   0
1551 1   3 4 5   0```

Table 11.10 shows part of the simulation results from the testbench, viterbi_test_CDD, in tabular form. Figure 11.5 shows the Verilog simulator output from the testbench (displayed using VeriWell from Wellspring).

 FIGURE 11.5  Viterbi encoder testbench simulation results. (Top) Initialization and the start of the encoder output sequence 2, 5, 4, 1, 0, ... on Y[2:0] at t = 151. (Bottom) The appearance of the same encoder output sequence at the output of the decoder, Out[2:0], at t = 1451, 1300 time units (13 positive clock edges) later.

The system input or message, `X[1:0]` , is driven by a counter that repeats the sequence 0, 1, 2, 3, ... incrementing by 1 at each positive clock edge (with a delay of one time unit), starting with `X` equal to 3 at t = 0. The active-high reset signal, `Res` , is asserted at t = 60 for 10 time units. The encoder output, `Y[2:0]` , changes at t = 151, which is one time unit (the positive-edge-triggered D flip-flop model contains a one-time-unit delay) after the first positive clock edge (at t = 150) following the deassertion of the reset at t = 70. The encoder output sequence beginning at t = 151 is 2, 5, 4, 1, 0, ... and then the sequence 5, 4, 1, 0, ... repeats. This encoder output sequence is then imagined to be transmitted and received. The receiver module calculates the distance measures and passes them to the decoder. After 13 positive clock-edges (1300 time ticks) the transmitted sequence appears at the output, `Out[2:0]` , beginning at t = 1451 with 2, 5, 4, 1, 0, ..., exactly the same as the encoder output.

## 11.12.4   Verilog Decoder Model

The Viterbi decoder model presented in this section is written for both simulation and synthesis. The Viterbi decoder makes extensive use of vector D flip-flops (registers). Early versions of Verilog-XL did not support vector instantiations of modules. In addition the inputs of UDPs may not be vectors and there are no primitive D flip-flops in Verilog. This makes instantiation of a register difficult other than by writing a separate module instance for each flip-flop.

The first solution to this problem is to use flip-flop models supplied with the synthesis tool such as the following:

`asDff #(3) subout0(in0, sub0, clk, reset);`

The asDff is a model in the Compass ASIC Synthesizer standard component library. This statement triggers the synthesis of three D flip-flops, with an input vector `ina` (with a range of three) connected to the D inputs, an output vector `sub0` (also with a range of three) connected to the Q flip-flop outputs, a common scalar clock signal, `clk` , and a common scalar `reset` signal. The disadvantage of this approach is that the names, functional behavior, and interfaces of the standard components are different for every software system.

The second solution, in new versions of Verilog-XL and other tools that support the IEEE standard, is to use vector instantiation as follows [LRM 7.5.1, 12.1.2]:

`myDff subout0[0:2] (in0, sub0, clk, reset);`

This instantiates three copies of a user-defined module or UDP called my` Dff` . The disadvantage of this approach is that not all simulators and synthesizers support vector instantiation.

The third solution (which is used in the Viterbi decoder model) is to write a model that supports vector inputs and outputs. Here is an example D flip-flop model:

```/******************************************************/
/*       module dff                                   */
/******************************************************/
/* A D flip-flop module. */
module dff(D,Q,Clock,Reset); // N.B. reset is active-low.
output Q; input D,Clock,Reset;
parameter CARDINALITY = 1; reg [CARDINALITY-1:0] Q;
wire [CARDINALITY-1:0] D;
always @(posedge Clock) if (Reset !== 0) #1 Q = D;
always begin wait (Reset == 0); Q = 0; wait (Reset == 1); end
endmodule```

We use this model by defining a parameter that specifies the bus width as follows:

dff #(3) subout0(in0, sub0, clk, reset);

The code that models the entire Viterbi decoder is listed below (Figure 12.6 on page 578 shows the block digram). Notice the following:

• Comments explain the function of each module.
• Each module is about a page or less of code.
• Each module can be tested by itself.
• The code is as simple as possible avoiding clever coding techniques.

The code is not flexible, because bit widths are fixed rather than using parameters. A model with parameters for rate, signal constellation, distance measure resolution, and path memory length is considerably more complex. We shall use this Viterbi decoder design again when we discuss logic synthesis in Chapter 12, test in Chapter 14, floorplanning and placement in Chapter 16, and routing in Chapter 17.

```/* Verilog code for a Viterbi decoder. The decoder assumes a rate
2/3 encoder, 8 PSK modulation, and trellis coding. The viterbi module
contains eight submodules: subset_decode, metric, compute_metric,
compare_select, reduce, pathin, path_memory, and output_decision.
The decoder accepts eight 3-bit measures of ||r-si||**2 and, after
an initial delay of thirteen clock cycles, the output is the best
estimate of the signal transmitted. The distance measures are the
Euclidean distances between the received signal r (with noise) and
each of the (in this case eight) possible transmitted signals s0 to s7.
Original by Christeen Gray, University of Hawaii. Heavily modified
by MJSS; any errors are mine. Use freely. */
/******************************************************/
/*   module viterbi                                   */
/******************************************************/
/* This is the top level of the Viterbi decoder. The eight input
signals {in0,...,in7} represent the distance measures, ||r-si||**2.
The other input signals are clk and reset. The output signals are
out and error. */
module viterbi
(in0,in1,in2,in3,in4,in5,in6,in7,
out,clk,reset,error);
input [2:0] in0,in1,in2,in3,in4,in5,in6,in7;
output [2:0] out; input clk,reset; output error;
wire sout0,sout1,sout2,sout3;
wire [2:0] s0,s1,s2,s3;
wire [4:0] m_in0,m_in1,m_in2,m_in3;
wire [4:0] m_out0,m_out1,m_out2,m_out3;
wire [4:0] p0_0,p2_0,p0_1,p2_1,p1_2,p3_2,p1_3,p3_3;
wire ACS0,ACS1,ACS2,ACS3;
wire [4:0] out0,out1,out2,out3;
wire [1:0] control;
wire [2:0] p0,p1,p2,p3;
wire [11:0] path0;
subset_decode u1(in0,in1,in2,in3,in4,in5,in6,in7,
s0,s1,s2,s3,sout0,sout1,sout2,sout3,clk,reset);
metric u2(m_in0,m_in1,m_in2,m_in3,m_out0,
m_out1,m_out2,m_out3,clk,reset);
compute_metric u3(m_out0,m_out1,m_out2,m_out3,s0,s1,s2,s3,
p0_0,p2_0,p0_1,p2_1,p1_2,p3_2,p1_3,p3_3,error);
compare_select u4(p0_0,p2_0,p0_1,p2_1,p1_2,p3_2,p1_3,p3_3,
out0,out1,out2,out3,ACS0,ACS1,ACS2,ACS3);
reduce u5(out0,out1,out2,out3,
m_in0,m_in1,m_in2,m_in3,control);
pathin u6(sout0,sout1,sout2,sout3,
ACS0,ACS1,ACS2,ACS3,path0,clk,reset);
path_memory u7(p0,p1,p2,p3,path0,clk,reset,
ACS0,ACS1,ACS2,ACS3);
output_decision u8(p0,p1,p2,p3,control,out);
endmodule
/******************************************************/
/* module subset_decode                               */
/******************************************************/
/* This module chooses the signal corresponding to the smallest of
each set {||r-s0||**2,||r-s4||**2}, {||r-s1||**2, ||r-s5||**2},
{||r-s2||**2,||r-s6||**2}, {||r-s3||**2,||r-s7||**2}. Therefore
there are eight input signals and four output signals for the
distance measures. The signals sout0, ..., sout3 are used to control
the path memory. The statement dff #(3) instantiates a vector array
of 3 D flip-flops. */
module subset_decode
(in0,in1,in2,in3,in4,in5,in6,in7,
s0,s1,s2,s3,
sout0,sout1,sout2,sout3,
clk,reset);
input [2:0] in0,in1,in2,in3,in4,in5,in6,in7;
output [2:0] s0,s1,s2,s3;
output sout0,sout1,sout2,sout3;
input clk,reset;
wire [2:0] sub0,sub1,sub2,sub3,sub4,sub5,sub6,sub7;
dff #(3) subout0(in0, sub0, clk, reset);
dff #(3) subout1(in1, sub1, clk, reset);
dff #(3) subout2(in2, sub2, clk, reset);
dff #(3) subout3(in3, sub3, clk, reset);
dff #(3) subout4(in4, sub4, clk, reset);
dff #(3) subout5(in5, sub5, clk, reset);
dff #(3) subout6(in6, sub6, clk, reset);
dff #(3) subout7(in7, sub7, clk, reset);
function [2:0] subset_decode; input [2:0] a,b;
begin
subset_decode = 0;
if (a<=b) subset_decode = a; else subset_decode = b;
end
endfunction
function set_control; input [2:0] a,b;
begin
if (a<=b) set_control = 0; else set_control = 1;
end
endfunction
assign s0 = subset_decode (sub0,sub4);
assign s1 = subset_decode (sub1,sub5);
assign s2 = subset_decode (sub2,sub6);
assign s3 = subset_decode (sub3,sub7);
assign sout0 = set_control(sub0,sub4);
assign sout1 = set_control(sub1,sub5);
assign sout2 = set_control(sub2,sub6);
assign sout3 = set_control(sub3,sub7);
endmodule
/******************************************************/
/*   module compute_metric                            */
/******************************************************/
/* This module computes the sum of path memory and the distance for
each path entering a state of the trellis. For the four states,
there are two paths entering it; therefore eight sums are computed
in this module. The path metrics and output sums are 5 bits wide.
The output sum is bounded and should never be greater than 5 bits
for a valid input signal. The overflow from the sum is the error
output and indicates an invalid input signal.*/
module compute_metric
(m_out0,m_out1,m_out2,m_out3,
s0,s1,s2,s3,p0_0,p2_0,
p0_1,p2_1,p1_2,p3_2,p1_3,p3_3,
error);
input [4:0] m_out0,m_out1,m_out2,m_out3;
input [2:0] s0,s1,s2,s3;
output [4:0] p0_0,p2_0,p0_1,p2_1,p1_2,p3_2,p1_3,p3_3;
output error;
assign
p0_0 = m_out0 + s0,
p2_0 = m_out2 + s2,
p0_1 = m_out0 + s2,
p2_1 = m_out2 + s0,
p1_2 = m_out1 + s1,
p3_2 = m_out3 + s3,
p1_3 = m_out1 + s3,
p3_3 = m_out3 + s1;
function is_error; input x1,x2,x3,x4,x5,x6,x7,x8;
begin
if (x1||x2||x3||x4||x5||x6||x7||x8) is_error = 1;
else is_error = 0;
end
endfunction
assign error = is_error(p0_0[4],p2_0[4],p0_1[4],p2_1[4],
p1_2[4],p3_2[4],p1_3[4],p3_3[4]);
endmodule
/******************************************************/
/*   module compare_select                            */
/******************************************************/
/* This module compares the summations from the compute_metric
module and selects the metric and path with the lowest value. The
output of this module is saved as the new path metric for each
state. The ACS output signals are used to control the path memory of
the decoder. */
module compare_select
(p0_0,p2_0,p0_1,p2_1,p1_2,p3_2,p1_3,p3_3,
out0,out1,out2,out3,
ACS0,ACS1,ACS2,ACS3);
input [4:0] p0_0,p2_0,p0_1,p2_1,p1_2,p3_2,p1_3,p3_3;
output [4:0] out0,out1,out2,out3;
output ACS0,ACS1,ACS2,ACS3;
function [4:0] find_min_metric; input [4:0] a,b;
begin
if (a <= b) find_min_metric = a; else find_min_metric = b;
end
endfunction
function set_control; input [4:0] a,b;
begin
if (a <= b) set_control = 0; else set_control = 1;
end
endfunction
assign out0 = find_min_metric(p0_0,p2_0);
assign out1 = find_min_metric(p0_1,p2_1);
assign out2 = find_min_metric(p1_2,p3_2);
assign out3 = find_min_metric(p1_3,p3_3);
assign ACS0 = set_control (p0_0,p2_0);
assign ACS1 = set_control (p0_1,p2_1);
assign ACS2 = set_control (p1_2,p3_2);
assign ACS3 = set_control (p1_3,p3_3);
endmodule
/******************************************************/
/*   module path                                      */
/******************************************************/
/* This is the basic unit for the path memory of the Viterbi
decoder. It consists of four 3-bit D flip-flops in parallel. There
is a 2:1 mux at each D flip-flop input. The statement dff #(12)
instantiates a vector array of 12 flip-flops. */
module path(in,out,clk,reset,ACS0,ACS1,ACS2,ACS3);
input [11:0] in; output [11:0] out;
input clk,reset,ACS0,ACS1,ACS2,ACS3; wire [11:0] p_in;
dff #(12) path0(p_in,out,clk,reset);
function [2:0] shift_path; input [2:0] a,b; input control;
begin
if (control == 0) shift_path = a; else shift_path = b;
end
endfunction
assign p_in[11:9] = shift_path(in[11:9],in[5:3],ACS0);
assign p_in[ 8:6] = shift_path(in[11:9],in[5:3],ACS1);
assign p_in[ 5:3] = shift_path(in[8: 6],in[2:0],ACS2);
assign p_in[ 2:0] = shift_path(in[8: 6],in[2:0],ACS3);
endmodule
/******************************************************/
/*   module path_memory                               */
/******************************************************/
/* This module consists of an array of memory elements (D
flip-flops) that store and shift the path memory as new signals are
added to the four paths (or four most likely sequences of signals).
This module instantiates 11 instances of the path module. */
module path_memory
(p0,p1,p2,p3,
path0,clk,reset,
ACS0,ACS1,ACS2,ACS3);
output [2:0] p0,p1,p2,p3; input [11:0] path0;
input clk,reset,ACS0,ACS1,ACS2,ACS3;
wire [11:0]out1,out2,out3,out4,out5,out6,out7,out8,out9,out10,out11;
path x1 (path0,out1 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x2 (out1, out2 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x3 (out2, out3 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x4 (out3, out4 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x5 (out4, out5 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x6 (out5, out6 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x7 (out6, out7 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x8 (out7, out8 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x9 (out8, out9 ,clk,reset,ACS0,ACS1,ACS2,ACS3),
x10(out9, out10,clk,reset,ACS0,ACS1,ACS2,ACS3),
x11(out10,out11,clk,reset,ACS0,ACS1,ACS2,ACS3);
assign p0 = out11[11:9];
assign p1 = out11[ 8:6];
assign p2 = out11[ 5:3];
assign p3 = out11[ 2:0];
endmodule
/******************************************************/
/*   module pathin                                    */
/******************************************************/
/* This module determines the input signal to the path for each of
the four paths. Control signals from the subset decoder and compare
select modules are used to store the correct signal. The statement
dff #(12) instantiates a vector array of 12 flip-flops. */
module pathin
(sout0,sout1,sout2,sout3,
ACS0,ACS1,ACS2,ACS3,
path0,clk,reset);
input sout0,sout1,sout2,sout3,ACS0,ACS1,ACS2,ACS3;
input clk,reset; output [11:0] path0;
wire [2:0] sig0,sig1,sig2,sig3; wire [11:0] path_in;
dff #(12) firstpath(path_in,path0,clk,reset);
function [2:0] subset0; input sout0;
begin
if(sout0 == 0) subset0 = 0; else subset0 = 4;
end
endfunction
function [2:0] subset1; input sout1;
begin
if(sout1 == 0) subset1 = 1; else subset1 = 5;
end
endfunction
function [2:0] subset2; input sout2;
begin
if(sout2 == 0) subset2 = 2; else subset2 = 6;
end
endfunction
function [2:0] subset3; input sout3;
begin
if(sout3 == 0) subset3 = 3; else subset3 = 7;
end
endfunction
function [2:0] find_path; input [2:0] a,b; input control;
begin
if(control==0) find_path = a; else find_path = b;
end
endfunction
assign sig0 = subset0(sout0);
assign sig1 = subset1(sout1);
assign sig2 = subset2(sout2);
assign sig3 = subset3(sout3);
assign path_in[11:9] = find_path(sig0,sig2,ACS0);
assign path_in[ 8:6] = find_path(sig2,sig0,ACS1);
assign path_in[ 5:3] = find_path(sig1,sig3,ACS2);
assign path_in[ 2:0] = find_path(sig3,sig1,ACS3);
endmodule
/******************************************************/
/*   module metric                                    */
/******************************************************/
/* The registers created in this module (using D flip-flops) store
the four path metrics. Each register is 5 bits wide. The statement
dff #(5) instantiates a vector array of 5 flip-flops. */
module metric
(m_in0,m_in1,m_in2,m_in3,
m_out0,m_out1,m_out2,m_out3,
clk,reset);
input [4:0] m_in0,m_in1,m_in2,m_in3;
output [4:0] m_out0,m_out1,m_out2,m_out3;
input clk,reset;
dff #(5) metric3(m_in3, m_out3, clk, reset);
dff #(5) metric2(m_in2, m_out2, clk, reset);
dff #(5) metric1(m_in1, m_out1, clk, reset);
dff #(5) metric0(m_in0, m_out0, clk, reset);
endmodule
/******************************************************/
/*   module output_decision                           */
/******************************************************/
/* This module decides the output signal based on the path that
corresponds to the smallest metric. The control signal comes from
the reduce module. */
module output_decision(p0,p1,p2,p3,control,out);
input [2:0] p0,p1,p2,p3; input [1:0] control; output [2:0] out;
function [2:0] decide;
input [2:0] p0,p1,p2,p3; input [1:0] control;
begin
if(control == 0) decide = p0;
else if(control == 1) decide = p1;
else if(control == 2) decide = p2;
else decide = p3;
end
endfunction
assign out = decide(p0,p1,p2,p3,control);
endmodule
/******************************************************/
/*   module reduce                                    */
/******************************************************/
/* This module reduces the metrics after the addition and compare
operations. This algorithm selects the smallest metric and subtracts
it from all the other metrics. */
module reduce
(in0,in1,in2,in3,
m_in0,m_in1,m_in2,m_in3,
control);
input [4:0] in0,in1,in2,in3;
output [4:0] m_in0,m_in1,m_in2,m_in3;
output [1:0] control; wire [4:0] smallest;
function [4:0] find_smallest;
input [4:0] in0,in1,in2,in3; reg [4:0] a,b;
begin
if(in0 <= in1) a = in0; else a = in1;
if(in2 <= in3) b = in2; else b = in3;
if(a <= b) find_smallest = a;
else find_smallest = b;
end
endfunction
function [1:0] smallest_no;
input [4:0] in0,in1,in2,in3,smallest;
begin
if(smallest == in0) smallest_no = 0;
else if (smallest == in1) smallest_no = 1;
else if (smallest == in2) smallest_no = 2;
else smallest_no = 3;
end
endfunction
assign smallest = find_smallest(in0,in1,in2,in3);
assign m_in0 = in0 - smallest;
assign m_in1 = in1 - smallest;
assign m_in2 = in2 - smallest;
assign m_in3 = in3 - smallest;
assign control = smallest_no(in0,in1,in2,in3,smallest);
endmodule```

Chapter start

Previous page

Next page