Viterbi decoder with pipelined ACS circuits

[0002] 1. Field of the Invention

[0003] The present invention relates generally to trellis-coded communications systems, and more specifically to Viterbi decoder having a high processing speed.

[0004] 2. Description of the Related Art

[0005] A Viterbi decoder with a code rate ½ and a constraint length 3 (four metric states) is disclosed in Japanese Laid-Open Patent Specification Hei-6-303153. The disclosed decoder includes a branch metric calculator and a pair of add/compare/select (ACS) circuits to which the outputs of the branch metric calculator are supplied on a time-shared basis. The outputs of the ACS circuits are stored back into memories as intermediate results of an ACS process to be updated with new branch metrics from the calculator. A maximum likelihood decision circuit compares path metrics from the ACS circuits to select path metrics of the most likely path in the trellis diagram.

[0006] In most data communication systems, however, the constraint length is usually 7 which implies that the metric states amount to as large as 64. If a Viterbi decoder with constraint length 7 were implemented using the prior art technique, it would be necessary to provide as many connections for the data path of the path metrics as there are state metrics. Since the access to the path metric memories is a dominant factor on the overall performance of the Viterbi decoder, a long queue would be formed in the ACS circuits if parallel mode of operation is implemented.

[0007] It is therefore an object of the present invention to provide a Viterbi decoder in which a high speed operation is achieved by having a plurality of ACS circuits operate continuously on a pipelined basis.

[0008] According to the present invention, there is provided a Viterbi decoder for receiving a sequence of convolutional codewords, comprising means for deriving a sequence of branch metrics from the received codeword sequence, and means for dividing the branch metric sequence into a plurality of branch metric sequences. A plurality of add/compare/select (ACS) circuits are provided for adding the branch metric sequences to a plurality ACS of previous path metrics and determining therefrom a plurality of sequences of path metrics of maximum likelihood paths and a plurality of indicators identifying the maximum likelihood paths. A pipelining circuit is provided for reordering, or pipelining state metrics of the path metrics of the maximum likelihood paths and supplying the pipelined state metrics to the ACS circuits. The indicators from the ACS circuits are used to recover an original bit sequence.

[0009] According to one embodiment, the pipelining circuit comprises a first bank of first and second memories and a second bank of first and second memories, and a control circuit for controlling the memories of the banks. During write operation, state metrics of respective path metric sequences from he ACS circuits are stored into the first and second memories of the first bank and state metrics of the respective path metric sequences are subsequently stored into the first and second memories of the second bank. During read operation, a first sequence of even-numbered state metrics and a second sequence of odd-numbered sate metrics are read from the first memory of the first bank and supplied to the ACS circuits, and a first sequence of odd-numbered state metrics and a second sequence of even-numbered state metrics are read from the second memory of the first bank and supplied to the ACS circuits, wherein the first sequence of even-numbered state metrics and the first sequence of odd-numbered state metrics form state metrics of consecutive numbers of a first group, and the second sequence of even-numbered state metrics and the second sequence of odd-numbered state metrics form state metrics of consecutive numbers of a second group following the consecutive numbers of the first group.

[0010] According to another embodiment, the pipelining circuit comprises a first bank of first, second, third and fourth memories and a second bank of first, second, third and fourth memories, and a control circuit for controlling the memories of the banks. During write operation, state metrics of respective path metric sequences from the ACS circuits are stored into the first, second, third and fourth memories of the first bank and state metrics of the respective sequences are subsequently stored into the first, second third and fourth memories of the second bank. During read operation, a first sequence of even-numbered state metrics is read from the first memory, a second sequence of odd-numbered state metrics is read from the second memory, a third sequence of even-numbered state metrics is read from the third memory, and a fourth sequence of odd-numbered state metrics is read from the fourth memory, the first and second sequences forming state metrics of consecutive numbers of a first group, and the third and fourth sequences forming state metrics of consecutive numbers of a second group following the consecutive numbers of the first group, wherein the state metrics read from the first and third memories of the first bank are supplied to a first group of the ACS circuits and the state metrics read from the second and fourth memories of the first bank are supplied to a second group of the ACS circuits.

[0011] The present invention will be described in further detail with reference to the accompanying drawings, in which:

[0012] FIG. 1 is a block diagram of a convolutional encoder used at the transmit end of a communication link for describing the Viterbi decoder of the present invention located at the receive end of the link;

[0013] FIG. 2 is a block diagram of a general configuration of the Viterbi decoder of the present invention;

[0014] FIG. 3 is a block diagram of a normalized branch metric calculator of the present invention;

[0015] FIG. 4 is a block diagram of a dividing circuit of the present invention;

[0016] FIG. 5ais a timing diagram of pulse sequences produced by a write address generator of the dividing circuit;

[0017] FIG. 5bis a timing diagram of pulse sequences produced by a read address generator of the dividing circuit and their relationships with two output sequences of branch metrics delivered from the dividing circuit;

[0018] FIG. 5cis a tabulation of relationships between the read address and branch metric pairs;

[0019] FIG. 6 is a block diagram of add/compare/select circuits of the present invention;

[0020] FIG. 7 is a block diagram of a reordering circuit of the present invention;

[0021] FIG. 8ais a table for mapping the relationships between read and write addresses used by the memories of the reordering circuit;

[0022] FIG. 8bis a table for mapping the contents of the memories of the reordering circuit to corresponding read/write addresses;

[0023] FIGS. 9a, 9band 9care tables mapping the relationships between encoder's operating states and decoder's branch metrics and path metrics;

[0024] FIG. 10 is a table for mapping the relationships between encoder's initial states and encoder's resultant states depending on input values for an example metric state;

[0025] FIG. 11 is a block diagram of a modified Viterbi decoder of the present invention;

[0026] FIG. 12 is a block diagram of the reordering circuit of the modified Viterbi decoder; and

[0027] FIG. 13 is a timing diagram of the various path metric sequences appearing in the reordering circuit of FIG. 12.

[0028] Before proceeding with the description of a Viterbi decoder of the present invention, it is useful to explain a convolutional encoder with a constraint length 7 and a code rate ⅓ with reference to FIG. 1. The convolutional encoder comprises a six-stage shift register 1, modulo-2 adders 2, 3 and 4, and a parallel-to-serial converter 5. The input terminals of stages D1 to D4 and the output terminal of stage D6 of shift register 1 are connected to adder 2 to produce a first output pulse sequence by operating a generator polynomial “1111001” on an input pulse sequence supplied to the input of the shift register 1. The input terminals of stages D1, D3, D4, D6 and the output terminal of stage D6 are connected to adder 3 to produce a second output pulse sequence by operating a generator polynomial “1011011” on the input pulse sequence. A third output pulse sequence is produced by coupling the input terminals of stages D1, D3, D5 and the output terminal of stage D6 to adder 4 by operating a generator polynomial “1110101” on the input pulse sequence. The pulses of these output sequences are multiplexed in the parallel-to-serial converter 5 into convolutional codewords.

[0029] In FIG. 2, the Viterbi decoder according to one embodiment of the present invention is illustrated. The decoder generally comprises a normalized branch metric calculator 12 to which convolutional codes at baseband are supplied through an input terminal 11. The calculator 12 produces normalized branch metrics from he received convolutional codewords and feeds a dividing circuit 13, where the branch metrics are divided into two branch metrics b₁and b₂. To the outputs of dividing circuit 13 are connected first and second add-compare-select (ACS) circuits 14aand 14b. ACS circuit 14aadds branch metric b₁to path metric p₁from a path metric pipelining or reordering circuit 15 and adds branch metric b₂to path metric p₂and produces a minimum path metric p₃and a path indicator c₁indicating the identity of the surviving path of the metric p₃. ACS circuit 14b, on the other hand, adds b₂to p₁and b₁to p₂and produces a minimum path metric p₄and a path indicator c₂the identity of the surviving path of the metric p₄. The path metrics p₃and p₄are supplied to the reordering circuit 15, where they are reordered into sequences p₁and p₂and fed back again to ACS circuits 14aand 14b, respectively.

[0030] The path indicators c₁and c₂are fed to shift registers 16aand 16b, respectively. At appropriate timing the path indicators are supplied from the shift registers to a path memory 17. A trellis decoder 18 is connected to the path memory 17 to perform a trellis search on the path indicators stored ion memory 17 to produce a replica of the input sequence applied to the convolutional encoder of FIG. 1.

[0031] Overall sequence control of the Viterbi decoder is provided by a controller 20 through control lines 21 to 29.

[0032] The convolutional codes received at the input terminal 11 are operated on a per-three-symbol basis, thus yielding the following eight (=2³) possible patterns:

[0033] Pattern 0 (1, 1, 1)

[0034] Pattern 1 (−1, 1, 1)

[0035] Pattern 2 (1, −1, 1)

[0036] Pattern 3 (−1, −1, 1)

[0037] Pattern 4 (1, 1, −1)

[0038] Pattern 5 (−1, 1, −1)

[0039] Pattern 6 (1, −1, −1)

[0040] Pattern 7 (−1, −1, −1)

[0041] Branch metric calculator 30 has a serial-to-parallel converter 40 where the input sequence is converted into parallel bits x_n, y_nand z_n. The Euclidean distance D between a received symbol sequence (x_n, y_n, z_n) and each branch metric pattern (r_0i, r_1i, r_2i) is determined by the following equation:

[0042] D=(x_n−r_0i)²+(y_n−r_1i)²+(z_n−r_2i)²  (1)

[0043] Using pattern 3, for example, equation (1) can be rewritten as:

[0044] D₃=(x_n²+2x_n+1)+(y_n²+2y_n+1)+(z_n²−2z_n+1)=(x_n²+y_n²+z_n²+3)−2(−x_n−y_n+z_n)  (2)

[0045] Similar calculations are performed on the rest of the eight patterns. Since the first term of equation (2) appears in the calculations of all branch metric patterns, it is only necessary to calculate the second term. The calculation of the second term is a process of inner product calculations between (x_n, y_n, z_n) and (r_0i, r_1i, r_2i).

[0046] As shown in detail in FIG. 3, the normalized branch metric calculator 12 comprises a branch metric calculator 30, a maximum likelihood value detector 31, a memory 32 and a subtractor 33.

[0047] Branch metric calculator 30 includes a serial-to-parallel converter 40 where the received convolutional code is converted into parallel bits x_n, y_nand z_n. In a practical embodiment, the inner product calculation is implemented by add/subtract circuits 41, 42 and 43 and a pattern generator 44, using two's complement notation. The parallel bits x_n, y_nand z_nfrom converter 40 are respectively supplied to add/subtract circuits 41, 42 and 43. The pattern generator 44 is a three-bit counter which is incremented by a clock pulse to cyclically produce the eight branch metric patterns for each set of input bits x_n, y_nand z_nand the elements r_0i, r_1i, r_2iof each pattern are supplied to add/subtract circuits 41, 42 and 43, respectively, as add-or-subtract command signals. To implement the two's complement calculation, a 0-bit input sequence is supplied from a 0-bit generator 45 to add/subtract circuit 41. The output of add/subtract circuit 41 is coupled to add/subtract circuit 42 whose output is, in turn, connected to add/subtract circuit 43.

[0048] The output of add/subtract circuit 43 is supplied to the maximum likelihood value detector 31. Detector 31 includes a comparator 50, a minimum selector 51 and a memory 52. Each of the eight branch metrics from the add/subtract circuit 43 is compared by the comparator 50 with a branch metric stored in the memory 52 to produce a command signal indicating which branch metric is smaller than the other. Minimum selector 51 responds to this command signal for selecting one of the input branch metric and the stored branch metric having a smaller value. The selected branch metric is stored into the memory 52 by replacing the previous one. The process is repeated until all the eight branch metrics are compared with each other. Controller 20 monitors control line 21 and begins counting each branch metric as the first pattern appears at the output of add/subtract 43. At the end of the comparison process, a branch metric of minimum value is stored in the memory 52 and then delivered to the subtractor 33 when the latter is activated by an enabling signal from controller 20 via line 22. Controller 20 then initializes the memory 52 via control line 23. Meanwhile, controller 20 commands the memory 32 via line 24 to set it in a write mode for storing the eight branch metrics and then causes it to read them out into the subtractor 33, where the branch metric of the maximum value is subtracted from each of the stored branch metrics. In this way, branch metrics of normalized value are delivered from subtractor 33 to the dividing circuit 13.

[0049] This normalization advantageously reduces the amount of information to be processed in later stages of the Viterbi decoder, in particular, to prevent path metrics from being overflowed from memories in the later stages of the Viterbi decoder.

[0050] As illustrated in FIG. 4, the dividing circuit 13 includes memories 60aand 60bto which the normalized branch metrics are supplied. The write and read addresses for these memories is produced by a write address generator 61 and a read address generator 62. The outputs of these address generators are alternately supplied to the memories 60a, 60bvia a switch 63.

[0051] Write address generator 61 has a pattern generator 65 for producing parallel bits x₁, x₂and x₃, representing eight bit patterns (FIG. 5a). An exclusive-OR gate 66 receives the x₁and x₃bits to produce an output y₁and an exclusive-OR gate 67 receives the x₂and x₃bits to produce an output y₂. As shown in FIG. 4a, the parallel bits y₁and y₂are in a cyclic pattern of decimal numbers 0, 1, 2 and 3 corresponding respectively to the decimal numbers 0, 1, 2 and 3 of the x-bit pattern and decimal numbers 3, 2, 1 and 0 corresponding respectively to the decimal numbers 4, 5, 6 and 7 of the x-bit pattern.

[0052] Controller 20 monitors the x₁, x₂and x₃bits via control lines 25 to determine the switch timing of switch 63 and the read/write timing of memories 60a, 60b.

[0053] When write address codes are generated for a series of eight bit patterns, a write command signal is applied to the switch 63 through line 26 for coupling the write address to the memories 60a, 60b, if these write address codes correspond to x-bit patterns 0, 1, 2 and 3, memory 60ais selected by a memory select (MS) supplied from controller 20 via line 27 and if they correspond to x-bit patterns 4, 5, 6 and 7, memory 60bis selected. Therefore, normalized branch metrics of patterns 0, 1, 2 and 3 are stored in memory 60aand those of patterns 7, 6, 5 and 4 are stored in memory 60bin the same storage locations as those in memory 60a. In other words, normalized branch metrics of patterns 0 and 7 form a pair and are stored in the same locations (i.e., y₁=0, y₂=0) of the respective memories 60aand 60b, and those of patterns 1 and 6 form a pair and are stored in the same locations (i.e., y₁=1, y₂=0) of memories 60aand 60b, and so forth.

[0054] The branch metrics stored pairwise in memories 60aand 60bare read out of these memories as branch metric sequences a₁(=0, 1, 2, 3) and a₂(=7, 6, 5, 4) by the read address generator 62 so that each pair of read branch metrics corresponds to each branch of the trellis diagram. Read address generator 62 comprises an encoder replica 68 and exclusive-OR gates 69 and 70 connected to the modulo-2 adders 2, 3, and 4 of the encoder replica.

[0055] Encoder replica 68 is of generally similar construction to the convolutional encoder of FIG. 1 with the exception that the six-stage shift register 1 is replaced with a 5-bit counter 1A and the first, second and third stages of the counter are connected to modulo-2 adder 2A and its output signal v₁(LSB) is supplied to the exclusive-OR gate 69. The counter's second, third and fifth stages are connected to adder 3A and its output signal v₂is supplied to the exclusive-OR gate 70, the counter's first, second and fourth stages being connected to adder 4aand its output signal v₃(MSB) being connected to the exclusive-OR gates 69 and 70. Exclusive-OR gates 69 and 70 produce output signals w₁and w₂which form a 2-bit read address code, the read address code being supplied through switch 63 to the memories 60aand 60b.

[0056] During the read mode, memories 60aand 60bare simultaneously selected by controller 20 in order to read the stored branch metrics in a pairwise fashion. In response to each two-bit address code, a pair of branch metrics is read pairwise from memories 60aand 60bduring the interval of metric states 0 to 31, as shown in FIG. 5b. Because of the two-parallel ACS operation for the 64 distinct metric states, the same bit patterns are repeatedly produced during the interval of metric states 32 to 63. Relationships between the two-bit read address codes and corresponding branch metric pairs are shown in FIG. 5c.

[0057] The output signal v₃of the read address generator is further supplied to a switching circuit 64 for establishing straight connections between memories 60aand 60band output terminals 71 and 72 when the signal v₃is at logic 0 and reversing the connections when the signal v₃is at logic 1. The normalized branch metrics sequences b₁and b₂and delivered to the ACS circuits via output terminals 71 and 72. The reason for reversing the connections between memories 60a, 60band terminals 71, 72 will be described later.

[0058] Since the convolutional encoder has a constraint length 7, the Viterbi decoder has 64 (=2⁷⁻¹) distinct states, or state metrics. The ACS circuits 14aand 14b, shown in detail in FIG. 6, perform add/compare/select computations simultaneously on two states at a time.

[0059] In the ACS circuit 14a, the branch metric sequences b₁and b₂are summed with path metrics p₁and p₂, respectively, to produce cumulative path metrics r₁and r₂at each state. A comparator 82 is connected to the outputs of the adders 80 and 81 for comparison between the path metrics r₁and r₂and produces an output signal c₁, indicating the identity of a surviving path p₃whose path metric is smaller than the other. This signal is applied to a selector 83 for selecting the surviving path metric p₃for coupling to the reordering circuit 15.

[0060] In the ACS circuit 14b, the branch metric sequences b₂and b₁are received by adders 84 and 85 where the sequences b₂and b₁are summed with path metrics p₁and p₂, respectively, to produce cumulative path metrics r₃and r₄at each state. A comparator 86 is connected to the outputs of the adders 84 and 85 where the cumulative path metrics r₃and r₄are compared with each other and an output signal c₂is produced, indicating the identity of a surviving path p₄having the smallest path metric. This signal is applied to a selector 87 for selecting the surviving path metric p₄for coupling to the reordering circuit 15. The survivors' path identity data c₁and c₂for each state are supplied to shift registers 16aand 16b,respectively.

[0061] Sequences of path metrics p₃and p₄are reordered in the reordering circuit 15 and then fed back to the ACS circuits as path metric sequences p₁and p₂for updating their metric values with new branch metrics. The updating operation of the ACS circuits will be discussed in detail later.

[0062] The reordering circuit 15 rearranges the sixty-four state metrics which are supplied from the ACS circuits 14aand 14bas intermediate results for the next decoding step. As shown in FIG. 7, the reordering circuit 15 is composed of two memory banks 92 and 93 for storing sixty-four state metrics and reading two state metrics at a time from each memory bank. Memory bank 92 consists of memories 92aand 92bwhich receive inputs from the ACS circuits via switches 93aand 93band supply their outputs to switches SW-A and SW-B. In like manner, memory bank 93 consists of memories 93aand 93bto receive inputs from switches 90, 91 and supply their outputs to switches SW-A and SW-B, respectively.

[0063] The switches SW-A and SW-B are operated by the controller 20 via line 28 so that the outputs of memory bank 92 are coupled to the ACS circuits 14aand 14bduring the interval of state metrics 0 to 31 and the outputs of memory bank 93 are coupled to the ACS circuits during the interval of state metrics 32 to 63. Memory banks 92 and 93 are in read and write modes, respectively, during the interval of state metrics 0 to 31 and in write and read modes, respectively, during the interval of state metrics 32 to 63. As illustrated in FIG. 7, the state metrics from ACS circuits 14aare interchanged with those from ACS circuit 14bat every two-state intervals by switches 90 and 91, and supplied to memory banks 92 and 93.

[0064] As shown in FIG. 8a, even-numbered state metrics 0 to 30 and odd-numbered sate metrics 33 to 63 are stored in memories 92aand 93a, and odd-numbered state metrics 1 to 31 and even-numbered state metrics 32 to 62 are stored in memories 92band 93b.

[0065] Such arrangements of the state metrics will be understood by considering a 6-stage shift register as follows.

[0066] Assume that the 6-stage shift register of the convolutional encoder of FIG. 1 is in a state “000000” (=state metric 0). The application of a bit “0” to the shift register simply shifts the all 0′ bits to the right, and so the state of the shift register remains unchanged, but changes to “100000” (=state metric 32) in response to the application of a bit “1”. If the shift register is in a state “000001” (=state metric 1), the application of a bit “0” to the shift register causes it to change to “000000” (=state metric 0), but changes to “100000” (=state metric 32) in response to the application of a bit “1”. In the above examples, parallel operations by ACS circuits 14aand 14bare achieved by reading state metric 0 from memory 92aand state metric 1 from memory 92band concurrently writing state metric 0 into memory 93aand state metric 32 into memory 93b. It will be seen from FIG. 6 that, in the next instant, state metrics 2 and 3 are read from memories 92aand 92b, while at the same time, state metrics 1 and 33 are written into memories 92aand 92b.

[0067] In order to achieve the read/write operation of memories 92 and 93 as discussed above, a 5-bit counter 94 is clocked to produce a 5-bit address code. The MSB to LSB of the address code are supplied to the MSB to LSB terminals 96 of a coupling circuit 95 as a read address and coupled to memories 92aand 92bas indicated by lines 100 when these memories are in a read mode and coupled to memories 93aand 93bas indicated by a dotted lines 101 when these memories are in a read mode.

[0068] To produce a write address for memories 93aand 92a, the MSB to the second LSB positions of the 5-bit address code of counter 94 are coupled to the second MSB to the LSB positions of terminals 97 of the coupling circuit 95 and the LSB of the code is supplied to the MSB position of terminals 97. The terminals 97 are coupled to the memory 93avia line 102 when this memory is in a write mode and coupled to the memory 92avia dotted line 103 when this memory is in a write mode.

[0069] As a write address for memories 93band 92b, the MSB to the second LSB positions of the 5-bit address code of counter 94 are coupled to the second MSB to the LSB positions of terminals 98 of the coupling circuit 95 and the LSB of the code is supplied via an inverter 99 to the MSB position of terminals 98. The terminals 98 are coupled to the memory 93bvia line 104 when this memory is in a write mode and coupled to the memory 92bvia dotted line 105 when this memory is in a write mode.

[0070] The coupling circuit 95 changes its configuration between the solid-line connections and the dotted-line connections in response to a control signl supplied on line 28 from the controller 20. This control signal is also used to set memories 92 and 93 in read and write modes, respectively, when the solid-line connections are established in the coupling circuit 95 and to set memories 92 and 93 in write and read modes, respectively, when the dotted-line connections are established in the coupling circuit 95. FIG. 8bshows the 5-bit read address codes successively generated by the counter 94 and the corresponding 5-bit write address codes supplied to memories 92 and 93.

[0071] Reverting to FIGS. 6 and 7, the updating operation of the path metric values in the ACS circuits will now be described below.

[0072] ACS circuit 14ais responsible for the updating of the states 0 to 31 of path metrics p₁and p₂, and ACS circuit 14bis responsible for the updating of the states 32 to 63 of these path metrics. Controller 20 has an index counter, now shown, which is set equal to 0 when state metrics 0 and 1 are read out of the memories 92aand 92binto both circuits at the beginning of a decoding cycle.

[0073] In the ACS circuit 14a, the adder 80 calculates a path metric r₁corresponding to a transition from state 0 to state 0 by adding a new branch metric b₁to path metric p₁, and the adder 81 calculates a path metric r₂corresponding to a transition from state 1 to state 0 by adding a new branch metric b₂to path metric p₂. Comparator 82 determines which of path metrics r₁and r₂has a smaller value and causes the selector 83 to select the smaller path metric as an updated state 0 of the surviving path metric p₃.

[0074] The transition from state 0 to state 0 corresponds to the application of a 0 to the shift register 1 of the FIG. 1 convolutional encoder in which all zero's are stored and the encoder produces an output sequence (0, 0, 0). Under this condition, branch metric 0 is supplied to the adder 80.

[0075] The transition form state 1 to state 0 corresponds to the application of a 0 to the shift register whose state is 0, 0, 0, 0, 0, 1 (=d1, D2, D3, D4 D5, D6) and the encoder produces an output sequence (1, 1, 1). Under this condition, branch metric 7 is supplied to the adder 81.

[0076] In the ACS circuit 14b, the adder 84 calculates a path metric r₃corresponding to a transition from state 0 to state 32 by adding the new branch metric b₂to path metric p₁, and the adder 85 calculates a path metric r₄corresponding to a transition from state 1 to state 32 by adding the new branch metric b₁to path metric p₂. Comparator 86 determines which of path metrics r₃and r₄has a smaller value and causes the selector 87 to select the smaller path metric as an updated state 32 of the surviving path metric p₄.

[0077] The transition from state 0 to state 32 corresponds to the application of a 1 to the shift register in which all zero's are stored and the encoder produces an output sequence (0, 0, 0). Under this condition, branch metric 7 is supplied to the adder 84.

[0078] The transition from state 1 to state 32 corresponds to the application of a 0 to the encoder' shift register whose stae is 0, 0, 0, 0, 0, 1 and the encoder produces an output sequence (0, 0, 0). Under this condition, branch metric 0 is supplied to the adder 85.

[0079] As the above process step is repeated, the controller's index counter is successively incremented from count 0, and at the end of the decoding cycle, the index counter reaches count 31. During each decoding cycle, state 0 to state 63 are updated.

[0080] The encoder's transition states 0 to 31 and their relationships to branch metrics a₁, a₂, b₁, b₂and path metrics p₁, p₃, p₂, p₄are illustrated in the tables of FIGS. 9a, 9band 9c.

[0081] It is appreciated that the branch metrics a₁and a₂are in reverse to corresponding branch metrics b₁and b₂for metric states 2, 3, 6, 7 ,8, 9, 12, 13, 16, 17, 20, 21, 26, 27, 30 and 31 as indicated by dotted rectangles. These switching circuit 64 (FIG. 4) performs switching operation in response to the output v₃of the encoder replica when these metric states occur (see also FIG. 5b).

[0082] The initial (shift register) state and the resultant state of the convolutional encoder in response to either a 0 or 1 are represented by:

[0083] Initial state=j(=D₁, D₂, D₃, D₄, D₅)i(=D₆)

[0084] Resultant state =i(=D₁)j(D₂, D₃, D₄, D₅, D₆)

[0085] where i=0 or 1, and j0 and j1 correspond respectively to path metrics p₁and p₂and 0j and 1j correspond respectively to path metrics p₃and p₄.

[0086] Therefore, the ACS circuit 14aperforms the following conversions:

[0087] M_k(j0)→λ(j0, 0j)→M_k+1(0j)

[0088] M_k(j1)→λ(j1, 0j)→M_k+1(0j)

[0089] The circuit 14bperforms the following conversions:

[0090] M_k(j0)→λ(j0, 1j)→M_k+1(1j)

[0091] M_k(j1)→λ(j1, 1j)→M_k+1(1j)

[0092] where M respresnets the previous path metric, λ represents the ACS computation, k=0, 1, . . . , K, and j=0, 1, . . . , 31. The value “j” respresnets the count value of the controller's index counter.

[0093] Taking metric state 26aas an example, it is seen from FIG. 10 that the following relations hold:

[0094] λ(j0, 0j)=λ(j1, 1j) and hence λ(p₁, p₃)=λ(p₂, p₄)

[0095] λ(j1, 0j)=λ(j0, 1j) and hence λ(p₂, p₃)=λ(p₁, p₄)

[0096] Since branch metric calculator 30, FIG. 3, determines Euclidean distances, the ACS circuits, in effect, calculates the following equations to select the minimum path metrics:

[0097] M_k+1(0j)=min{M_k(j0)+λ(j0, 0j), M_k(j1)+λ(j1, 0j)}

[0098] M_k+1(1j)=min{M_k(j0)+λ(j0, 1j), M_k(j1)+λ(j1, 1j)}

[0099] A modified embodiment of the Viterbi decoder is shown in FIG. 11. According to this modification, four ACS circuits 14a, 14b, 14cand 14dare provided for performing add/compare/select operations on four metric states at a time in a parallel mode. ACS circuits 14aand 14bperform updating operations on path metrics p₁and p₃from a path metric reordering circuit 150 to store updated path metrics p₅and p₆back into the reordering circuit 150, and circuits 14cand 14dupdates path metrics p₂and p₄to store updated path metrics p₇and p₈back into the reordering circuit 150. The normalized branch metric sequences b₁and b₂are supplied to all the All ACS circuits. Indicators c₁, c₂, c₃and c₄of surviving paths are generated by ACS circuits 14ato 14dand respectively fed to shift registers 16ato 16d, and then loaded into the path memory 17.

[0100] As illustrated in FIG. 12, the path metric reordering circuit 150 includes a memory bank 201 of four memories 201ato 201dand a memory bank 206 of memories 206ato 206d. An address generator 200 supplies 4-bit address codes to all the memories, so that when memories of bank 201 are in a read mode, the memories of bank 206 are in a write mode, and vice versa. Path metric p₁is formed by selectively connecting the outputs of memories 201aand 206athrough a switch SW-A to the ACS circuit 14a. Path metric p₂is formed by selectively connecting the outputs of memories 201band 206bthrough a switch SW-B to the ACS circuit 14c. In like manner, path metric p₃is formed by selectively connecting the outputs of memories 201cand 206cthrough a switch SW-C to the ACS circuit 14b, path metric p₄being formed by selectively connecting the outputs of memories 201dand 206dthrough a switch SW-D to the ACS circuit 14d.

[0101] Path metrics p₅and p₆from ACS circuits 14aand 14bare respectively connected to cross-coupling switches 204 and 205. ACS circuit 14cproduces a path metric sequence p₇which is one-clock interval delayed by a delay element 202 and applied to cross-coupling switch 204, and similarly, ACS circuit 14cproduces a path metric sequence p₈which is one-clock interval delayed by a delay element 203 and applied to cross-coupling switch 205. Path metric p₅and the delayed a path metric p₇are cross-coupled through switch 204 to either memory 206aas a path metric p₉or to memory 206cas a path metric p₁₁. Path metrics p₆and the delayed path metric p₈are cross-coupled through switch 205 to either memory 206bas a path metric p₁₀or to memory 206das a path metric p₁₂. Path metrics p₉, p₁₀, p₁₁and p₁₂are also supplied to memories 201a, 201b,201cand 201d, respectively.

[0102] Controller 20 operates the switch SW-A to SW-D and the read/write timing of all the memories through control line 28 to produce the path metrics p₁to p₁₂. Cross-coupling switches 204 and 205 are controlled by the address generator 200 to alternately connect their input sequences to their output terminals.

[0103] As shown in FIG. 13, path metric sequence p₁is formed by even-numbered state metrics 0 to 30 and path metric sequence p₂is formed by odd-numbered state metrics 1 to 31. Path metric sequence p₃is composed of even-numbered state metrics 32 to 62 and path metric sequence p₄is composed of odd-numbered state metrics 33 to 63.

[0104] From state metrics 0 to 32 of path metric sequences p₁and p₃, ACS circuit 14aproduces state metric 0 and ACS circuit 14bproduces state metric 32. By using state metrics 1 and 33 of sequences p₂and p₄, ACS circuit 14cproduces state metric 16 of sequence p₇and circuit 14dproduces a state metric 48 of sequence p₈. As a result, the state metrics 0 and 32 are supplied to memories 206aand 206bas path metric sequences p₉and p₁₀, respectively, and the state metrics 16 and 48 are supplied to memories 206aand 206bduring the next clock interval. During the next clock interval, state metrics 1 (p₅), 33 (p₆), 17 (p₇) and 49 (p₈) are produced and state metrics 1 (p₅) and 33 (p₆) are supplied to memories 206cand 206das sequences p₁₁and p₁₂, respectively.

[0105] A total of 18 clock intervals is required to complete the ACS operations on state metrics 0 to 63. This total clock interval favorably compares with a total time of 132 clock intervals which is taken by the serial processing.