Method and Apparatus for Implementing a Maximum-Likelihood Decoder in a Hypercube Network

2. Field of the Invention

The present invention is concerned with a method for maximum-likelihood decoding of convolutional codes on a network of microprocessors, and apparatus for executing this method.

3. Brief Description of the Prior Art

A concurrent computing system in which individual computers, each with a computational processor and a message-handling processor, are connected as a hypercube is described and claimed in an application entitled "Concurrent Computing System Through Asynchronous Communication Channels, Ser. No. 754,828, filed on July 12, 1985 and assigned to California Institute of Technology. As there described, N nodes (numbered 0, 1,--N-1) are connected together in a binary (or Boolean) n-dimensional cube in which N=2.sup.n or n=log.sub.2 N. The above-identified application depicts one representative hypercube connection of a network of processors in which the processors are located at the vertices of an n-dimensional cube and communicate with each other by bidirectional communication links only along the edges of the cube. One manner of transmitting data and representative examples of microprocessor hardware and software suitable for performing the data transfer feature of this invention is fully disclosed in the above-identified application.

Hypercube-connected multiprocessors having up to 128 nodes (n=7) are known, and will soon be extended to 1,024 nodes (n=10) and higher. As the number of nodes increases, it is imperative that the number of connections per decoder at each node be kept to a minimum. Otherwise, the existing pin-limitation constraint of VLSI decoders cannot be accommodated.

Maximum-likelihood decoding of convolutional codes is also well known. The Viterbi decoding algorithm is commonly used for such decoding, and many textbooks such as "Theory and Practice of Error Control Codes" by Richard E. Blahut, Addison-Wesley Publishing Company, Inc. Copyright 1983 describe the encoding/decoding of convolutional codes. A Viterbi decoding algorithm is conceptualized in the text and a succinct summary of a trellis diagram, stages, stages and common steps to obtain accumulated metrics and survivors is described at pages 350 through 353 and 377 through 382 of that text.

Convolutional codes are widely used in digital communication systems to decrease the probability of error on a given noisy channel (coding gain). They are characterized by the constraint length K and by the code rate given by the ratio k.sub.0 /n.sub.0, where n.sub.0 channel symbols are generated by the encoder for each k.sub.0 input data bits. Details can be found, for example, in the above-noted "Theory and Practice of Error Control Codes," by R. E. Blahut.

Convolutional codes can achieve large coding gain if they use large memory m, or equivalently, large constraint length K=m+k.sub.0. An encoder for such codes is a finite-state machine with 2.sup.m states. The complexity of a maximum-likelihood decoder is approximately proportional to the number of states, i.e., it grows exponentially with m.

The task of the decoder is to consider all possible paths on a trellis of about 5m stages, and find the most likely path, according to a specified goodness criterion. The goodness criterion is described in the article "The Viterbi Algorithm," by G. D. Forney, Proc. IEEE, Vol. 61 (1973), pp. 263-278.

Multiprocessor systems have the potential to obtain large computation power. This is possible if one can solve the problem of how to decompose the decoding algorithm. There are two key requirements in the problem decomposition: (1) divide the algorithm in equal parts, in order to share equally the resources available in each processor, and (2) minimize the communication between the parts, so that each processor needs to share information only with nearest neighbors.

Since a single microprocessor or VLSI chip cannot accommodate all the functions required to implement complex decoders, methods must be found to efficiently use a network of processors. Parallel decoding is accomplished by a network of processors with each processor connected as the edges of an n-dimensional cube. The paths to be examined and stored by each processor are shared only with neighboring processors on the cube. Each neighbor is interrogated to find the goodness of the updated paths and therefore decide which ones should be stored.

The most basic embodiment assigns each available processor to each single state of the decoder. The proper reordering of paths and states is obtained by making a given processor x act as state x, where x is a function of x and the stage of the trellis, based on cyclic shifts of the binary label representing x.

The method also provides a way to group sets of S=2.sup.s states into each processor still requiring only communication between neighboring processors. This arrangement yields high computational efficiency for complex codes.

It is a feature of the invention to provide a method and apparatus for maximum-likelihood decoding of convolutional codes on a network of microprocessors interconnected as a n-dimensional cube and having each processor compute part of all paths of a trellis diagram in parallel with concurrent computations by other processors in the cube. This feature results in high efficiency, in terms of decoding speed, and allows use of codes more complex than those presently decodable with known methods.

In accordance with the present invention, a method is provided for decoding convolutional codes, by the accumulated metric and survivor steps of the known Viterbi algorithm, but with the novel and unique difference that decoding operations are performed in parallel by a network of processors placed at the vertices of an n-dimensional cube, and bidirectionally communicating with neighboring processors only along the edges of the cube. This decoding method can operate with high efficiency because the parallel decoding operations concerning each state of the decoder are performed in a suitable and novel order within each processor.

Further provided is an arrangement for implementing this novel method, comprising a decoder structure which is characterized by:

a network of N=2.sup.n processors interconnected as an n-dimensional cube, having bidirectional communication along the edges of the cube for receiving/transmitting to neighboring processors accumulated metrics and hypothesized data sequences (survivors), to internally store said quantities, and to perform comparisons between accumulated metrics;

input means for sending the received channel symbol sequence to all processors in the network; and

output means for delivering the decoded, most likely, data sequence to a user.

The arrangement can accommodate different numbers S=2.sup.s of the M=2.sup.m decoder states into each processor, depending on the code complexity and the number of available processors N=2.sup.m, where M=S.times.N.

FIG. 1 is a trellis diagram of the Viterbi algorithm, showing all the possible state transitions for an 8-state decoder (M=2.sup.m =8, m=3). Only four stages are shown, but the trellis can be extended as necessary;

FIG. 2 is the hypercube trellis diagram of this invention showing transitions between processors P.sub.i of the hypercube and the states represented by each processor. The trellis can be extended by repeating the m stages shown, to form a periodic structure;

FIG. 3 is an example of an n-dimensional cube (n=3) network of microprocessors placed at the vertices of the cube, where solid lines show connections used in a given stage;

FIG. 4 is a specific decoder structure where two states are representated by each of the four processors;

FIG. 5 is a block diagram of the internal arrangement of each processor in the network;

FIG. 6, including FIGS. 6a, 6b, and 6c, contains the arrangements for decoders with M=8 states and S=1, 2, or 4 states per processor, respectively;

FIG. 7a is a decoder structure on a two-dimensional cube for an 8-state (m=3) code of k.sub.o /n.sub.o, where k.sub.o =2;

FIG. 7b is a decoder trellis for an 8-state (m=3) code of rate k.sub.o /n.sub.o, where k.sub.o =2;

FIG. 8a is a trellis diagram of a four state decoder showing how paths are eliminated according to the usual Viterbi algorithm. and

FIG. 8b is a trellis diagram for four states showing how paths are eliminated during the decoding operation of this invention.

Convolutional codes are well known. Such codes can achieve large coding gain, i.e., improvement on the overall performance of a digital communication link, if they use large memory m, or equivalently, large constraint length K=m+1 (in the simple case when k.sub.o =1). An encoder for such codes is a finite-state machine with 2.sup.m states. Decoders for convolutional codes can be effectively described in terms of a graph called a trellis diagram, as shown in FIG. 1 for an m=3, 8-state code.

The left-hand column of FIG. 1 shows all of the possibilities for a three-bit grouping in a finite state coding machine of three shift register cells, or memory m=3. In keeping with the Viterbi decoding algorithm, a decoder would examine all eight possibilities by using an iterative trial. Each iteration corresponds to a separate vertical column such as iteration No. 1, No. 2, etc., through 15. The number of iterations in a time sequence, with time being depicted horizontally, is shown in FIG. 1 for 15 iterations. It is a rule of thumb that 15=5m iterations will almost always yield the proper result. Obviously more iterations can be tried, but the extra number of iterations normally does not achieve any significantly-improved results.

The task of the decoder is to consider all possible paths on a trellis of about 5m stages, and find the most likely path, according to a specified goodness criterion. The goodness criterion is simply a number of merit which will be explained in more detail hereinafter for a typical simplified example of FIG. 8. Suffice it to say at this point that a received sequence of symbols is viewed by the decoder as simply a trial of hypothesized sequences. As each new received symbol is considered, the weighted values of trellis paths are reviewed by the decoding algorithm and the lowest number (indicating the highest level of goodness) is temporarily chosen as the best possible candidate to match the one that was originally encoded.

The trellis diagram 10 in FIG. 1 is used in the Viterbi algorithm to represent all possible transitions between states as described in the above-mentioned articles. In particular, at each stage all eight states are examined and only one of the two possible paths 11, 12 coming into a state (such as 000) is preserved, along with its goodness or likelihood measure, called an accumulated metric. At a given time (stage), such as time T.sub.1, each state is associated with one (and only one) path (path 12, for example) reaching it. The algorithm performs the following steps:

(1) Update the value of the accumulated metric of the two paths converging into each state, according to a known rule This known rule, described in detail in the above-referenced paper by Forney consists, in summary, of adding the so-called branch metric, which depends on the received symbol, to the accumulated metrics of the paths converging into each state;

(2) Choose the preferred path between those two, according to their metrics; and

(3) Store the chosen path and its metric.

Before describing the trellis for the processor/decoder method and apparatus of this invention, a brief review of the simplified diagram of FIG. 3 is believed helpful. The earlier-identified application discloses a complete concurrent processing system in which bidirectional communication links transmit data along the edges of a cube. For simplicity sake each mode, or processor, is shown simply as a dot. In FIG. 3, the bidirectional communication links are shown as solid lines with double-headed arrows 30.sub.x through 33.sub.x, 35.sub.z through 38.sub.z and 40.sub.y through 43.sub.y, respectively. The x, y and z indicate directions of communication in the cube. Associated with the corner locations of the cube network are binary labels which identify the processors. For example, processor P.sub.0 is identified by the tribit group 000, P.sub.1 by the tribit group 001, etc. Each processor P.sub.000 (P.sub.0) through P.sub.111 (P.sub.7 is connected only to its n neighbors. It is desirable to use direct communication links between processors, in order to speed up communication. Bidirectional link 30.sub.x delivers bit sequences back and forth between processors P.sub.0 and P.sub.1 in any well-known manner. Likewise, as shown, link 31.sub.x is connected between P.sub.4 and P.sub.5, link 32.sub.x is connected between P.sub.6 and P.sub.7, and link 33.sub.x is connected between P.sub.2 and P.sub.3. In the second stage of FIG. 3, bidirectional link 35.sub.z is connected between processors P.sub.0 and P.sub.2, link 36.sub.z is connected between P.sub.4 and P.sub.6, etc. as is there depicted.

Since complex codes have a very large number of states, it becomes impossible to perform sequentially all the above steps in reasonable time with a single processor. It is therefore desirable to share the work-load among many processors working in parallel. A convenient topology for a network of processors is the n-dimensional cube structure described above. Processors must be able to communicate among themselves in order to exchange intermediate results. Therefore, the decoding process will include some time spent in computations internal to each processor, and some time for interprocessor communication. It is this latter communication time which must be kept as small as possible to yield high decoding efficiency.

The advantage which can be achieved by the invention is the ability to use large constraint length convolutional codes, which yield high coding gain and to keep acceptable decoding speed with feasible hardware.

This is due to the fact that the efficiency of the method, given by ##EQU1## where N.sub.o is the number of parallel metric comparisons, t.sub.o is the comparison time, N.sub.t is the number of parallel survivor exchanges, and t.sub.t is the exchange time. The efficiency remains high even when a large number of processors are used.

While t.sub.o and t.sub.t depend on the hardware technology used for the processors, the method yields

so that the efficiency is always above the ratio ##EQU2## which is reached when N=M.

We assign each state of FIG. 1 to a different processor, so that all operations concerning all states can be done simultaneously (in parallel) at each stage, and sequentially stage by stage. Upon examination, however, I discovered that if we assign state 0 to processor P.sub.0, state 1 to processor P.sub.1, and so on up to state N-1 to processor P.sub.N-1 (P.sub.7) and we consider processors connected as in FIG. 3, then links between processors which are not directly connected in FIG. 3 would be necessary to implement all links between the states or processors in FIG. 1. My novel solution included mapping the states in the trellis 10 of FIG. 1 as the hypercube trellis 20 of FIG. 2.

According to the principles of my invention, a given processor is not assigned to a fixed state, as was the case in FIG. 1. Instead, for my invention the processors are identified by a binary label (P.sub.0 =P.sub.000, P.sub.1 =P.sub.001, etc.) as shown in FIG. 2, and the trellis labelling and stage order is uniquely defined by the following formula. In particular, processor x represents state x at stage k, if

where .rho..sup.(k) (.) is the cyclic right shift of x by k binary positions. A path through given states in FIG. 1 is thus represented by a specified equivalent path in FIG. 2, which passes through the same states. This means that there is a well-defined correspondence between paths in FIGS. 1 and 2. According to this correspondence, a Viterbi-type algorithm, based on the trellis of FIG. 1, can be performed on the hypercube trellis of FIG. 2.

The interesting and useful property of the trellis diagram of FIG. 2 is that all the required links between processors are now exactly those available in the hypercube network of FIG. 3. The first stage labeled as such in FIG. 3 shows how the first stage of FIG. 2 can be performed by using the connections 30.sub.x through 33.sub.x (marked with solid lines and double-headed arrows) between processors P.sub.0, P.sub.1 and P.sub.2, P.sub.3 and P.sub.4, P.sub.5 and P.sub.6, P.sub.7, respectively. Similarly, the second and third stages of FIG. 3 show the bidirection communication lines required for implementation of the second and third stages of FIG. 2. It should be understood that the embodiment of the decoder on the network has been explained for the case m=3, but it clearly can be generalized to other decoder sizes and hypercube dimensionality.

When the number of states is larger than the available or feasible number of processors, it becomes necessary to assign more than one state per processor. This can be done as shown in FIG. 4, where S=2 states are assigned to each processor. The required interprocessor communication links are provided by a two-cube-connected processor system which requires two decoding operations within each state. The method and apparatus of this invention thus generalizes to a number of states per processor which is a power of two, i.e., S=2.sup.s, where S is the number of states per processor.

The simplest embodiment of the invention is shown in FIG. 5 for the case of one state per processor S=1. The block diagram represents the arrangement used in each processor of the hypercube, where the input and output devices 60 and 65 sequentially connect to neighbors along each dimension of the cube, one dimension at a time, as shown by stages 1, 2 and 3 of FIG. 3. The block diagram of FIG. 5 may be thought of as a particular means for performing the several desired functions. FIG. 5 is a timed operation which is readily performable by any well-known and available processor, and to this extent FIG. 5 may be thought of as a flow diagram for the various computations.

Although not depicted, it should be understood that all processors are initialized to the same initial state. Operation of the decoder requires that blocks of initializing data be loaded in every processor by an operation called "broadcasting." In the hypercube network of processors under consideration, data from a host processor is directly exchanged only through node zero (the origin of the cube). An efficient concurrent method is required to broadcast a message from node zero to all other nodes. Since the diameter D of an n-cube is n, a lower bound on the broadcasting time is n time units (where the unit is the time to send a message to a neighbor).

Assume that a message is in node zero, at time zero. In each subsequent time slot t.sub.k send messages in parallel from each node

to each node

the neighbors along dimension k. After n time units, the message has propagated to all nodes.

Even though this method does not minimize the number of communications (with the advantage of a very simple indexing), it optimizes the total broadcasting time to n time units. The result is clearly optimum, since it achieves the lower bound.

At the start of the hypercube decoding algorithm, input device 60 loads a received channel sequence to be decoded into a suitable storage device 69. As noted earlier, the preferred embodiment of this invention is achieved by VLSI techniques. Thus the storage device 69 may advantageously be an addressable storage space in the processor memory. A sequence of processor computations are then performed by the decoder. The input sequence, stored in memory 69, is used to update both a locally-stored accumulated metric and an accumulated metric that has been received from a neighboring processor. The local metric is stored in a local metric memory 70. That metric value is then updated in the update metric device 71.

Meanwhile, an accumulated metric value from a neighboring processor has been supplied by input device 60 to an accumulated metric storage 75 which is used to store the neighbor's accumulated metric value. The metric at storage 75 is updated and made available in the update metric unit 76. A suitable comparison between those updated metric values is achieved by comparator 72 and the proper metric value is retained as a new local metric value. Note that comparator 72 supplies that new local metric value both to the local metric memory 70 and to the output device 65.

A comparable operation takes place for the survivor values. Thus, input device 60 receives the survivor value from the current neighbor, i.e., the neighbor along the dimension currently in use. That survivor value is stored at 80 and updated at 81. The survivor is simply updated by a table look-up method performed in accordance with the well-known Viterbi algorithm. For this reason no control lead is shown for update circuits 81 and 86.

An updated local survivor and an updated neighbor survivor are supplied to a comparator 90 in order to choose the most likely path. The result of the comparison under control of the selection command from comparison circuit 72 is used to select either the updated local survivor or the updated neighbor survivor in 90. The selected quantities (metric and survivor) are thereafter fed back and stored in the processor as the next upcoming local quantities. Note that both are also available to be sent, via output 65, to a neighbor processor along the appropriate dimension of the cube.

The decoded sequence is formed from the survivors as in the known Viterbi algorithm and is stored in a decoded register sequence 95. The decoded sequence output from storage 95 is delivered to a user. Note that input and output leads are labeled at the origin node in FIG. 3.

In FIG. 6a the trellis diagram is as that shown earlier in FIG. 2 and thus needs no further description. FIG. 6b describes the implementation of the same decoder of FIG. 62a, but with two states per processor (S=2). Note that double lines mean that an exchange of two metrics and two survivors along each bidirectional link between processors is required. Similarly, in FIG. 6c, each processor performs all the operations on a set of four states (S=4).

When more than one state is assigned to each processor, the invention can be applied to the decoding of a more general class of codes having rate k.sub.o /n.sub.o where k.sub.o >1. FIG. 7 shows a structure for decoding an 8-state code with k.sub.o =2 on a two-dimensional cube with four processors. Again, all the required links in the trellis of FIG. 7a can be implemented on a 2-cube as in FIG. 7b.

FIG. 8 is an example showing how various paths are eliminated during decoding. The solid line in FIGS. 8a and 8b is the path which has been chosen.

Consider, as an example, a decoder for a 4-state rate one-half convolutional code given by the generator polynominals g.sub.1 =111 and g.sub.2 =101. Such a received sequence is given in FIG. 8b.

A conventional decoder searches for the maximum-likelihood path on the graph of FIG. 8a where, for a given received sequence, all survivor paths considered are shown. The decoder of my invention operates as shown in FIG. 8b, where the same survivor paths are shown in terms of transitions between processors. The decoded sequence is obviously the same in both cases, but the transitions in FIG. 8b involve only neighboring processors on a hypercube.

While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention.