Viterbi decoding apparatus and viterbi decoding method

[0002] 1. Field of the Invention

[0003] The invention relates to a Viterbi decoding apparatus and a Viterbi decoding method which is used for a maximum likelihood decoding method of a convolution code that is used for, for example, a satellite broadcasting or the like.

[0004] 2. Description of the Related Art

[0005] As one of methods of decoding the convolution code, a Viterbi decoding method is known. The Viterbi decoding method is a maximum likelihood decoding method for the convolution code, whereby an error correction is executed by selecting a series (hereinafter, such a series is referred to as a maximum likelihood path) which is the nearest to a received code series from code series which can be formed from an encoder on a transmission side. That is, a transition diagram (hereinbelow, referred to as a trellis) which is formed on the basis of an encoding method by the encoder on the transmission side is used as a prerequisite. For example, a transition in which a hamming distance from the received code series is the shortest is selected from transitions as a maximum likelihood path which can occur on the transition diagram.

[0006] A Viterbi decoding apparatus for executing the Viterbi decoding method comprises: a branch metric calculating circuit for calculating a branch metric, namely, a hamming distance between a path which reaches each state on the trellis and the received code series in response to a clock; an ACS circuit for calculating a state metric on the basis of the branch metric, comparing values of the state metrics, and selecting a maximum likelihood path; a normalizing circuit for normalizing the value of the state metric; a state metric storing circuit for storing the value of the state metric; and a path memory circuit for forming decoding data in accordance with a selection result by the ACS.

[0007] In this instance, as a path memory circuit, there are two kinds of circuits of a circuit for executing a register transition method of transferring path selection contents by using a register train and a circuit for executing a method of storing the path selection contents by using an RAM and tracing the storage contents, thereby decoding. Those two kinds of methods will now be described hereinbelow.

[0008] In the register transition method which has been used in the general Viterbi decoding apparatus, memory cells each comprising a selector and a register are arranged on the trellis in the path memory circuit and the contents in the register are transferred on the basis of path selection information which is outputted from the ACS circuit. By selecting an output of a maximum likelihood state among outputs of memory cells at the final stage, information for the maximum likelihood path is selected and decoding data is outputted.

[0009] Although such a register transition method has an advantage such that a high speed operation can be executed, there is a drawback such that when a cut length increases, a circuit scale becomes very large. Particularly, since an application such that the cut length exceeds 100 has recently been presented, the increase in circuit scale becomes a serious problem.

[0010] In recent years, a method of decoding by storing path information by using an RAM (Random Access Memory) and tracing the stored information has been being actively studied. Such a method will now be called a trace-back method hereinlater.

[0011] As a method of terminating the encoding of the convolution code, a termination has been known. When the terminated convolution code is Viterbi decoded, the maximum likelihood path can be obtained by decoding by tracing back a path from a state of all 0. In the Viterbi decoding apparatus which has been used so far, when the terminated convolution code is successively received, the decoding is executed by the normal operation in many cases.

[0012] In such a decoding method, there is a problem such that when the next convolution code is continuously inputted subsequently to the terminated convolution code, a strict maximum likelihood decoding cannot be executed, so that there is a fear that a decoding error occurs. Since this problem is caused by a point that a termination interval is not considered when the Viterbi decoding is performed, the problem also occurs in both of the above-mentioned register transition method and the trace-back method.

[0013] The invention is proposed in consideration of such a circumstance. It is, therefore, an object of the invention to provide a Viterbi decoding apparatus and a Viterbi decoding method which can execute a strict maximum likelihood decoding even for a terminated convolution code.

[0014] Methods and systems consistent with the present invention provide a Viterbi decoding apparatus for continuously receiving a terminated convolution code, comprising terminate state path decoding means for certainly decoding a path which reaches a state to be terminated.

[0015] Methods and systems consistent with the present invention also provide a Viterbi decoding method for continuously receiving a terminated convolution code, comprising terminate state path decoding step of certainly decoding a path which reaches a state to be terminated.

[0016] According to the invention as mentioned above, since the path which reaches the state to be terminated can be certainly decoded, it is possible to execute a maximum likelihood decoding for the terminated convolution code.

[0017] The above, and other, objects, features and advantage of the present invention will become readily apparent from the following detailed description thereof which is to be read in connection with the accompanying drawings.

[0018] FIG. 1 is a block diagram for explaining a whole construction of an embodiment of the invention;

[0019] FIG. 2 is a block diagram for explaining a transition diagram when the restriction length=3;

[0020] FIG. 3 is a block diagram depicting a conventional of the state metric storing circuit shown in FIG. 1;

[0021] FIG. 4 is a schematic diagram for explaining a memory cell of a path memory in a register transition method;

[0022] FIG. 5 is a schematic diagram for explaining an arrangement of memory cells in the path memory in the register transition method;

[0023] FIG. 6 is a schematic diagram for explaining a termination;

[0024] FIG. 7 is a schematic diagram showing an example of a convolution encoder of a restriction length=3;

[0025] FIGS. 8A and 8B are schematic diagrams for explaining a trellis at the time of the termination and a decoding error in a Viterbi decoding apparatus which has conventionally been used;

[0026] FIG. 9 is a block diagram for explaining a path memory circuit in the first embodiment of the invention;

[0027] FIG. 10 is a block diagram for explaining a path memory circuit in the second embodiment of the invention;

[0028] FIG. 11 is a schematic diagram for explaining a principle of the tracing in a trace-back method;

[0029] FIG. 12 is a schematic diagram for explaining a method of the tracing in the trace-back method;

[0030] FIG. 13 is a schematic diagram depicting a role of each RAM in a conventional trace-back method in accordance with the present invention;

[0031] FIG. 14 is a schematic diagram depicting a memory operation in the conventional trace-back method in accordance with the present invention;

[0032] FIG. 15 is a block diagram for explaining a path memory circuit in the third embodiment of the invention;

[0033] FIG. 16 is a block diagram for explaining a path memory circuit in the fourth embodiment of the invention; and

[0034] FIG. 17 is a schematic diagram for explaining a metric for a path from state 00.

[0035] The first embodiment of the invention will now be described hereinbelow with reference to the drawings. First, a whole construction of the first embodiment of the invention will now be explained with reference to FIG. 1. The first embodiment of the invention comprises: a branch metric calculating circuit 701; an ACS circuit 702; a normalizing circuit 703; a state metric storing circuit 704; and a path memory circuit 705. When data received from a transmission side through a transmission path is inputted, a maximum likelihood path is selected from a code series which can be formed from an encoder on the transmission side and decoding data is formed on the basis of selection contents.

[0036] That is, for example, a transition diagram (hereinbelow, referred to as a trellis) as shown in FIG. 2 which is formed on the basis of an encoding method by the encoder on the transmission side is used as a prerequisite and, for example, a path whose hamming distance from a received code series is the shortest is selected as a maximum likelihood path from the transitions which can occur on the transition diagram.

[0037] When a reception data signal s701 is inputted, the branch metric calculating circuit 701 calculates a branch metric of the reception data and outputs a calculation result as a branch metric signal s702. On the basis of the branch metric signal s702 and a state metric signal s705 which is inputted from the state metric storing circuit 704, the ACS circuit 702 adds the branch metric and the state metric to each of two paths which join to a certain state, compares those addition values, selects the addition value having a higher likelihood on the basis of a comparison result, and sets it as a new state metric.

[0038] Such selected contents are outputted as path selection information s706, the number of a state having the minimum state metric is outputted as a maximum likelihood state signal s707, and a newly obtained state metric is outputted as a new state metric signal s703.

[0039] A method of selecting the path will now be described with respect to a case where a restriction length=3. A trellis of FIG. 2 has four states 00, 01, 10, and 11 and indicates an example of the trellis in the case where the restriction length=3. An arrow indicates a path which can occur every time slot. A path corresponding to decoding data ‘0’ is shown by a broken line. A path corresponding to decoding data ‘1’ is shown by a solid line. Two paths which join exist in each of all states every time slot. A hamming distance (branch metric) between the reception signal and the path and an accumulation sum (state metric) of the branch metrics so far are added to each of the two paths which join to a certain state, addition results are compared, and the value having a higher likelihood is selected on the basis of a comparison result.

[0040] The normalizing circuit 703 normalizes by using a method of subtracting the minimum state metric from the new state metric signal s703 which is outputted from the ACS circuit 702 or the like, sets a normalized value to a value within a preset range, and outputs it as a normalization state metric signal s704. The state metric storing circuit 704 stores the normalization state metric signal s704 which is outputted from the normalizing circuit 703 and returns it as a state metric signal s705 to the ACS circuit 702. An example of a construction of the state metric storing circuit 704 is shown in FIG. 3. It is assumed that the storing circuit 704 has four registers in correspondence to the four states in the trellis of FIG. 2. Although each of the four registers is a register of five bits in FIG. 3, a register of the other number of bits can be also used.

[0041] Subsequently, prior to explaining the path memory circuit 705 in the first embodiment of the invention, to make an understanding easy, a construction of a general path memory circuit to realize the register transition method will now be described. FIG. 5 shows a construction of a path memory circuit in which the memory cells each comprising the selector and register as shown in FIG. 4 are arranged in the trellis shown in FIG. 2. In FIG. 5, the memory cell is shown by MS. In the above construction, by transferring the contents of the register on the basis of the path selection information which is outputted from the ACS circuit 702, information corresponding to a survival path from each state is preserved in the register of each memory cell. Therefore, a decoding in which the trellis shown in FIG. 2 is used as a prerequisite, namely, a decoding by the register transition method in the case where there are four states and the restriction length=3 and the cut-length=4 is realized.

[0042] In such a general path memory circuit, there is a problem such that a strict maximum likelihood decoding cannot be performed when the terminated convolution codes are continuously received. This problem will now be described hereinbelow. A method of inputting 0 of the number (restriction length-1) to the encoder after all of the information bits were inputted in order to terminate the encoding of the convolution codes is known (refer to FIG. 6). The process to set the state of the encoder to all 0 at a predetermined time point as mentioned above is called “terminate”. The number of times until the end of the termination after the start of the encoding is called “termination length”.

[0043] In case of Viterbi decoding the terminated convolution code, by decoding by tracing back the path from the state of all 0, the maximum likelihood path can be obtained. In the actual Viterbi decoding apparatus, however, in case of continuously receiving the terminated convolution codes, the decoding is often performed by an ordinary operation.

[0044] In such a decoding method, however, when the next convolution code is continuously inputted subsequently to the terminated convolution code, there is a case where the strict maximum likelihood decoding cannot be performed. Such a case will now be described hereinbelow. In case of using a convolution encoder of the restriction length=3 as shown in FIG. 7, a case where the next encoding is subsequently executed after the code was terminated will now be considered. An example of the trellis in this case is shown in FIG. 8A. FIG. 8A shows a trellis which is traced in the case where the code subsequent to the terminating interval is decoded by tracing back the path from the state of all 0, thereby obtaining the maximum likelihood path.

[0045] A case where a correct path is a path (Pr in FIG. 8B) of all 0 will now be considered. In this case, if the decoding is performed without considering the termination, there is a fear such that an error path Pe as shown in FIG. 8B is decoded. This is because as for the error path Pe, since a Hamming distance from the path Pr of all 0 is small to be 6, a probability such that it is erroneously set to a decoding result is relatively high.

[0046] Now, assuming that the error path Pe was erroneously decoded, even if the decoding bits in an interval where the termination is executed are ignored, an error of one bit is included in the information bits regarding the transmission information. Since this path does not exist on the inherent terminated trellis, if the strict maximum likelihood decoding is performed in consideration of the terminating interval, such a decoding error does not occur.

[0047] FIG. 9 shows a construction of the path memory circuit 705 in the first embodiment of the invention in which the strict maximum likelihood decoding is performed in consideration of the terminating interval from a viewpoint of the above circumstances. In addition to a train of the memory cells as many as the cut length arranged in correspondence to each state, the path memory circuit 705 has a register train 102 and a control circuit 101 controls the register train 102 on the basis of the termination information.

[0048] That is, outputs of selectors at the first stage, second stage, third stage, and fourth stage in the register train corresponding to state 00 are inputted to a register 1021 and selectors 1022, 1024, and 1026 in the register train 102, respectively. Outputs of registers 1021, 1023, and 1025 at the front stages are inputted to the selectors 1022, 1024, and 1026, respectively. Each of the selectors 1022, 1024, and 1026 outputs one of the data which is inputted to the register at the post stage in response to a command of the control circuit 101.

[0049] Information corresponding to the survival path of each state is stored into the register by transferring in accordance with the path selection information of each state which is inputted from the ACS circuit 702. In an interval until the reception word is terminated, by selecting the output of the maximum likelihood state among the outputs at the final stages, the information corresponding to the maximum likelihood path is selected and the decoding data is outputted. In this interval, for example, ‘1’ is outputted from the control circuit to the register train 102 and a decoding word corresponding to state 0 is also stored in the register train 102.

[0050] On the other hand, when the reception word is terminated, the signal from the control circuit 101 to the register train 102 is switched to, for instance, ‘0’, thereby allowing the information stored in the register train 102 to be transferred as it is. By a selecting circuit 103 at the final stage, the output of the register train 102 is outputted as it is as a decoding word. By such an operation, the path which reaches state 00 can be decoded when the reception word is terminated.

[0051] For an interval when the contents of the register 102 are outputted, each of the other four register trains newly starts the ordinary transition corresponding to the subsequent convolution code, returns the operation to the ordinary decoding operation simultaneously with that all of the contents of the register train 102 are outputted, and switches the signal from the control circuit 101 to ‘0’. In the first embodiment of the invention as mentioned above, even in the case where the terminated convolution codes are continuously inputted, the path which reaches the state to be terminated can be decoded while continuing the decoding operation. Thus, the terminated code can be also strictly maximum likelihood decoded and a decoding error rate can be improved.

[0052] The second embodiment of the invention using a path memory circuit 805 having a construction different from the first embodiment of the invention will now be described. FIG. 10 shows the construction of the path memory circuit 805 in the second embodiment of the invention. When performing the decoding of the restriction length-3 and the cut-length=4, the path strict maximum likelihood decoding even for the terminated reception word.

[0053] In the path memory circuit 805, in the train of the memory cells as many as the cut length arranged in correspondence to each state, the signal which is inputted to a selector of each memory cell in a register train 203 corresponding to state 00 is controlled by a control circuit. That is, selectors 204, 205, 206, and 207 are provided and the path selection information and ‘0’ are inputted to those selectors. In response to a command from a control circuit 201, each of the selectors 204 to 207 inputs one of the path selection information and ‘0’ as a control signal to the selector of each memory cell in the register train 203.

[0054] The following operation is realized by such a construction. That is, for an interval until the reception word is terminated, the path selection information is given as a control signal to the register train 203 of state 00 and the ordinary register transition is performed. Among the outputs at the final stages, by selecting the output of the maximum likelihood state, information corresponding to the maximum likelihood path is selected and the decoding data is outputted. On the other hand, at the clock, when the reception word is terminated, it is controlled so that the selectors 204 to 207 give ‘0’ as control signals for the resister train 203 of state 00. The storage contents at this clock are transferred as they are.

[0055] In the next clock, the selector 204 gives the path selection information to the selector of the memory cell at the first stage and the selectors 205 to 207 give ‘0’ to the selectors of the memory cells at the second and subsequent stages. Further in the next clock, the selectors 204 and 205 give the path selection information to the selectors of the memory cells up to the second stage. The selectors 206 and 207 give ‘0’ to the selectors of the memory cells at the third and subsequent stages. In a manner similar to the above, the control signals are sequentially switched by the number of signals corresponding to the cut length. Upon termination, until the output of the decoding words stored in the register train of state 00 is completed, a selecting circuit 202 at the final stage generates the output from state 00 as decoding data.

[0056] For a period of time until the output of the decoding words stored in the register train of state 00 is finished, the path memory executes the ordinary operation to the convolution code which is subsequently inputted. Therefore, simultaneously with the end of the decoding of the terminated code, the operation can be returned to the ordinary decoding.

[0057] As mentioned above, in the second embodiment of the invention as well, even when the terminated convolution codes are continuously inputted, the path which reaches the state to be terminated can be decoded while continuing the decoding operation.

[0058] The first and second embodiments of the invention mentioned above relate to the register transition method as a prerequisite. The decoding error which can occur in the case where the terminated convolution codes are continuously inputted also similarly becomes a problem in a Viterbi decoding apparatus for performing a decoding by the trace-back method. The third embodiment of the invention, therefore, to solve the problem in the trace-back method will now be described. For easy understanding, the general trace-back method which has been used hitherto will be first described.

[0059] The principle operation of the trace in the trace-back method will now be described with respect to the case where the restriction length=3 as an example. In FIG. 11, a case of tracing from state 01 will be considered. States having a possibility of the transition to state 01 are state 00 and state 10. When the path on the state 00 side has been selected, 0 is stored in the path memory. When the path on the state 10 side is selected, 1 (namely, the most significant bit of the previous state) is stored in the path memory.

[0060] Even in case of transferring from any state, the input is 1 and it is expressed by the least significant bit of state 01. From the above explanation, it is sufficient to execute the tracing operation as follows. As shown in FIG. 12, the least significant bit of trace starting state in which the tracing is started is set to the decoding bit. The number of the next tracing state which is traced subsequently to the trace starting state is formed by newly adding the bit in the path memory as a most significant bit to the bits from the most significant bit to the lower second bit of the trace starting state. By such an operation, the selected path can be traced from the state in which the minimum state metric is obtained.

[0061] To make the Viterbi decoding apparatus operative at a high speed, the RAM can be accessed only once every clock. Explanation will be made with respect to a case of using a path memory circuit having four memories of a single port in order to perform the decoding for each RAM by an access of one time. In the following description, the restriction length=3 of the code and the cut length=4 are used as a prerequisite. A path memory circuit which is used in this case is a path memory circuit having four RAMs of a single port having the bit number (in this example, four bits) as many as the number of states and the word number (in this example, four words) corresponding to the cut length.

[0062] The path selection information as much as the number of states is inputted every clock from the ACS circuit 702 to the path memory circuit. As for the four RAMs, the following four roles (1) to (4) are sequentially switched every clocks (in this case, four clocks) corresponding to the cut length (refer to FIG. 13). An example of the operation of each of the four RAMs based on such an operation is shown in FIG. 14.

[0063] (1) The path selection information is sequentially written.

[0064] (2) The tracing is sequentially performed on the basis of the written path selection information. The decoding is not performed.

[0065] (3) No access

[0066] (4) The tracing is sequentially performed from the trace result in (2) and the decoding bits are outputted.

[0067] The decoding by the trace-back method is realized by the construction and operation of the path memory circuit.

[0068] In the Viterbi decoding apparatus for performing the trace-back method as mentioned above, the third embodiment of the invention to solve the foregoing problem regarding the termination of the convolution code will now be described. FIG. 15 shows a construction of a path memory circuit 905 in the third embodiment of the invention. The path memory circuit 905 is a path memory circuit for performing the decoding by the trace-back method by using four RAMs of a single port of four bits and four words in the case where the decoding in which (the cut-length)=(the termination length/4)=4 is performed to the code of the restriction length=3 and the termination length=16. It is now assumed that the start time point of writing the path selection information to the RAM is matched to the start time point of the encoding.

[0069] As for RAMs 30, 31, 32, and 33, the writing of path selection information s302 which is inputted from the ACS circuit and the reading of the stored path selection information are performed in response to a control signal s303 which is formed by a control circuit 301 and read path selection information s304, s305, s306, and s307 is inputted to the control circuit 301. In a manner similar to the conventional method, the operation of the memory until the reception word is terminated is executed by switching the following roles.

[0070] (1) The path selection information is sequentially written.

[0071] (2) The tracing is sequentially executed on the basis of the written path selection information. The decoding is not performed.

[0072] (3) No access

[0073] (4) The tracing is sequentially performed from the trace result in (2) and the decoding bits are outputted.

[0074] When the terminated interval is decoded, the RAM for performing the role of (4) starts the tracing from state 00 instead of the tracing result of (2) and the decoding is performed. Therefore, the control circuit 301 switches the operation of each RAM in accordance with a termination signal s301. Since the starting time point for encoding is matched with the starting time point for writing into the RAM and there is a relation such that the cut-length is equal to ¼ of the termination length, the timing to finish the termination coincides with the timing to start the tracing. Even during the decoding of the terminated interval, the tracing of the portion of (2) for decoding the next interval is executed. Therefore, simultaneously with that the end of the decoding of the terminated code, the operation can be returned to the ordinary decoding operation.

[0075] A signal s308 decoded by the tracing in (4) is inputted to an output buffer 302 and is rearranged in accordance with the order of the inherent time series. After that it is outputted as a decoding bit signal s309. As mentioned above, in the third embodiment of the invention as well, even when the terminated convolution codes are continuously inputted, the path which reaches the state to be terminated can be decoded while continuing the decoding operation.

[0076] The foregoing first, second, and third embodiments of the invention intend to solve the problem regarding the termination in the path memory circuit. On the other hand, the fourth embodiment of the invention which can solve the problem regarding the termination in the state metric storing circuit will now be described hereinbelow. A whole construction of the fourth embodiment of the invention is similar to those of the first embodiment and the like of the invention mentioned above. A construction of a state metric storing circuit 1004 in the fourth embodiment of the invention is shown in FIG. 16. The state metric storing circuit 1004 is a storing circuit of a state metric in the case where when a code of a restriction length=3 is decoded, a branch metric of 4 bits and a state metric of 5 bits are set.

[0077] Selectors 401, 402, 403, and 404 are provided at the front stage of four registers for storing state metrics of the paths which reach states 00, 01, 10, and 11. A value of the normalized state metric is inputted from the normalizing circuit to each selector. A value 0 is further inputted to the register 401 corresponding to state 00. A value 31 (the maximum value which is expressed by 5 bits) is further inputted to the selectors 402 to 404 corresponding to the other states. Termination information is inputted to the selectors 401 to 404 and each selector outputs the state metric and one of the values 0 and 31 on the basis of the termination information. A clipping is performed at the value 31 so that the state metric does not overflow in the ACS circuit 702.

[0078] In the state metric storing circuit 1004, the selectors 401 to 404 output the values of the state metrics to registers at the post stages, respectively, for a period of time until the reception word is terminated. Thus, the ordinary decoding such that the state metrics are sequentially updated and the decoding data before the cut-length is outputted is performed. On the other hand, when the reception word is terminated, each selector outputs a value other than the value of the state metric to each register at the post stage.

[0079] Therefore, the state metric of state 00 is initialized to 0 and the state metrics of the other states are initialized to 31. Since the branch metric for one clock consists of four bits, as shown in FIG. 17, the values of the branch metrics in periods P51 and P52 are equal to or less than 15 (the maximum value which is expressed by 4 bits), the number of metrics for the path in which state 00 is used as a start point is equal to or less than 30 for a period of time (namely, after the elapse of the periods P51 and P52) of two clocks after the start of the new convolution code. Thus, the path from state 00 is certainly selected.

[0080] Even if the subsequent operation is executed in a manner similar to the ordinary decoding operation and the decoding is performed while tracing back by an interval corresponding to the cut-length, as for the decoding at the timing when the termination is performed, the maximum likelihood path is certainly selected from the paths which pass state 00. Even in the fourth embodiment of the invention as mentioned above, when the terminated convolution codes are continuously inputted as well, the path which reaches the state to be terminated can be decoded while continuing the decoding operation.

[0081] In the first embodiment and the like of the invention mentioned above, although the case where the restriction length=3 and the cut-length=4 has been described, the invention can be applied to a case where the restriction length and cut-length have arbitrary values.

[0082] As mentioned above, the invention intends to perform the Viterbi decoding in consideration of the terminating interval of the reception word. Thus, the maximum likelihood decoding can be performed for the terminated convolution code.

[0083] Having described specific preferred embodiments of the present invention with reference to the accompanying drawings, it is to be understood that the invention is not limited to those precise embodiments, and that various changes and modifications may be effected therein by one skilled in the art without departing from the scope or the spirit of the invention as defined in the appended claims.