Soft-output decoding

[0001] The present invention relates to a soft-output decoding apparatus and method, and a decoding apparatus and method, suitable for repetitive decoding.

[0002] These years, studies have been made to minimize the symbol error rate by making soft-output of a result of decoding of an inner code in a concatenated code and a result of each repetitive decoding based on the repetitive decoding method, and suitable decoding methods for the error rate minimization have actively been studied. As a typical example, there is already known the BCJR algorithm proposed by Bahl, Cocke, Jelinek and Raviv in their “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate” (IEEE Trans. Inf. Theory, vol. IT-20, pp. 284–287, March 1974). The BCJR algorithm does not output each symbol as a result of decoding but it outputs the likelihood of each symbol. Such an output is called “soft-output”. What the BCJR algorithm is will be described below. In the following description, it will be assumed that as shown in FIG. 1, an encoder 1001 included in a transmitter (not shown) makes convolutional coding of digital information, and the output of the transmitter is supplied to a receiver (not shown) via a noisy non-storage communications channel 1002, and decoded, for observation, by a decoder 1003 included in the receiver.

[0003] First, a number M of states (transition state) representing the content of a shift register included in the encoder 1001 are denoted by m(0, 1, . . . , M-1), and a state at a time t is denoted by S_t. On the assumption that k-bit information is supplied in one time slot, an input at the time t is denoted by i_t=(i_t1, i_t2, . . . , i_tk) and an input sequence is denoted by I_t^T=(i₁, i₂, . . . , i_T). In case there is a transition from a state m′ to a state m at this time, an information bit corresponding to the transition is denoted by i(m′, m)=(i₁(m′, m), i₂(m′, m), . . . , i_k(m′, m)). Further, on the assumption that an n-bit code is outputted in one time slot, an output at the time t is denoted by X_t=(x_t1, x_t2, . . . . , x_tn) and an output sequence is denoted by X₁^T=(x₁, x₂, . . . , x_T). In case there is a transition from the state m′ to the state m at this time, a code bit for the transition is denoted by X(m′, m)=(x₁(m′, m), x₂(m′, m), . . . , x_n(m′, m)).

[0004] It is assumed that the convolutional coding by the encoder 1001 begins with a state S₀=0 and ends with S_T=0 with outputting X₁^T. The probability P_t(m|m′) of a transition from one state to another is defined by the following expression (1):
P_t(m|m′)=Pr{S_t=m|S_t−1=m′}  (1)

[0005] Note that in the right side of the expression (1), Pr{A|B} is a conditional probability in which A will occur under the same conditions as those under which B has occurred. The probability of transition P_t(m|m′) is equal to the probability Pr{i_t=i} in which the input i_t at the time t is i when the input i transits from the state m′ to state m, as will be seen from the following expression (2):
P_t(m|m′)=Pr{i_t=i}  (2)

[0006] Supplied with X₁^T as an input, the noisy non-storage communications channel 1002 outputs Y₁^T. On the assumption that an n-bit received value is outputted in one time slot, an output at the time t will be y_t=(y_t1, y_t2, . . . , y_tn) and the output of the channel will be Y₁^T=(y₁, y₂, . . . , y_T). The transition probability of the noisy non-storage channel 1002 can be defined by a transition probability Pr{y_j|x_j} of each symbol for all times t(1≦t≦T) as given by the following expression (3):

[0007] $\begin{array}{cc}\mathrm{Pr}\{Y_1^tX_1^t\}=\prod _{j=1}^t\mathrm{Pr}\{y_jx_j\}& \left(3\right)\end{array}$

[0008] The likelihood of input information at a time t when Y₁^T is received is denoted by λ_tj as defined by the following expression (4). This is the very thing to be determined, namely, a soft-output.

[0009] $\begin{array}{cc}{\lambda }_{tj}=\frac{\mathrm{Pr}\{i_{\mathrm{tj}}=1Y_1^T\}}{\mathrm{Pr}\{i_{\mathrm{tj}}=0Y_1^T\}}& \left(4\right)\end{array}$

[0010] In the BCJR algorithm, probabilities α_t, β_t and γ_t as shown in the following expressions (5) and (7) are defined. Note that Pr{A; B} is a probability in which both A and B will occur.
α_t(m)=Pr{S_t=m;Y₁^t}  (5)
β_t(m)=Pr{Y_t+1^T|S_t=m}  (6)
γ_t(m′,m)=Pr{S_t=m; y_t|S_t−1=m′}  (7)

[0011] What these probabilities α_t, β_t and γ_t are will be described with reference to FIG. 2 showing a trellis which provides a diagram of state transition taking place in the encoder 1001. In FIG. 2, α_t−1 corresponds to a probability of passing by each state at a time t−1 computed from a coding start state S₀=0 in time sequence on the basis of a received value; β_t corresponds to a probability of passing by each state at a time t computed from a coding termination state S_T=0 in reverse time sequence on the basis of the received value; and γ_t corresponds to a probability of reception of an output of each branch runs from one state to another at the time t computed on the basis of a received value and input probability at the time t.

[0012] Using these probabilities α_t, β_t and γ_t, the soft-output λ_tj can be given by the following expression (8):

[0013] $\begin{array}{cc}{\lambda }_{\mathrm{tj}}=\frac{\sum _{i_j\left(\begin{array}{c}{m}^{\prime },m\\ m^{\prime },m\end{array}\right)=1}{\alpha }_t\left(m^{\prime }\right){\gamma }_t\left(m^{\prime },m\right){\beta }_t\left(m\right)}{\sum _{i_j\left(\begin{array}{c}{m}^{\prime },m\\ m^{\prime },m\end{array}\right)=0}{\alpha }_t\left(m^{\prime }\right){\gamma }_t\left(m^{\prime },m\right){\beta }_t\left(m\right)}& \left(8\right)\end{array}$

[0014] The relation among the times t=1, 2, . . . , T can be given by the following expression (9):

[0015] $\begin{array}{cc}{\alpha }_t\left(m\right)=\sum _{m^{\prime }=0}^{M-1}{\alpha }_{t-1}\left(m^{\prime }\right){\gamma }_t\left(m^{\prime },m\right)\mathrm{where}{\alpha }_0\left(0\right)=1,{\alpha }_0\left(m\right)=0\left(m\ne 0\right).& \left(9\right)\end{array}$

[0016] The above relation among the times t=1, 2, . . . , T can also be given by the following expression (10):

[0017] $\begin{array}{cc}{\beta }_t\left(m\right)=\sum _{m^{\prime }=0}^{M-1}{\beta }_{t+1}\left(m^{\prime }\right){\gamma }_{t+1}\left(m,m^{\prime }\right)\mathrm{where}{\beta }_T\left(0\right)=1,{\beta }_T\left(m\right)=0\left(m\ne 0\right).& \left(10\right)\end{array}$

[0018] Further, the probability γ_t can be given by the following expression (11):

[0019] $\begin{array}{cc}{\gamma }_t\left(m^{\prime },m\right)=\{\begin{array}{c}{P}_t(mm^{\prime })·\mathrm{Pr}\{y_tx\left(m^{\prime },m\right)\}\\ =\mathrm{Pr}\left\{i_t=i\left(m^{\prime },m\right)\right\}·\mathrm{Pr}\{y_tx\left(m^{\prime },m\right)\}\\ :\mathrm{Transition}\mathrm{from}{m}^{\prime }\mathrm{to}m\mathrm{with}\mathrm{input}i\\ 0:\mathrm{No}\mathrm{tr}\mathrm{ansition}\mathrm{from}{m}^{\prime }\mathrm{to}m\mathrm{with}\mathrm{input}i\end{array}& \left(11\right)\end{array}$

[0020] Therefore, to adopt the BCJR algorithm for the soft-output decoding, the decoder 1003 determines a soft-output λ_t based on the above-mentioned relations by running through a sequences of operational steps in a flow chart shown in FIG. 3.

[0021] First in step S1001 shown in FIG. 3, each time the decoder 1003 receives y_t, it computes probabilities α_t(m) and γ_t(m′, m) based on the above expressions (9) and (11).

[0022] Next in step S1002, after receiving all data in the sequence Y₁^T, the decoder 1003 computes a probability β_t(m) of each state m at all times t on the basis of the above expression (10).

[0023] Then in step S1003, the decoder 1003 computes the soft-output λ_t at each time t by placing, into the above expression (8), the probabilities α_t, β_t and γ_t having been computed in steps S1001 and S1002.

[0024] Going through the above sequences of operational steps, the decoder 1003 can make the soft-output decoding by adopting the BCJR algorithm.

[0025] It should be reminded here that the BCJR algorithm has a problem that since the computational operations have to be done with a probability being held as it is as a value and include a product operation, so this algorithm needs large amounts of computation. To reduce the amounts of computation, there are available the Max-Log-MAP and Log-Map algorithms (will be referred to as “Max-Log-BCJR algorithm” and “Log-MCJR algorithm”, respectively, hereunder) proposed by Robertson, Villebrun and Hoeher in their “A Comparison of Optimal and Sub-optimal MAP Decoding Algorithms Operating in the Domain” (IEEE Int. Conf. on Communications, pp. 1009–1013, June 1995).

[0026] First, the Max-Log-BCJR algorithm will be explained. In this algorithm, the probabilities α_t, β_t, and γ_t and the soft-output λ_t are logarithmically notated by natural logarithms, respectively, the product operation for the probabilities is replaced with a logarithmic-sum operation as shown in the following expression (12), and the sum operation for the probabilities is approximated by computation of a logarithmic maximum value as shown in the following expression (13). Note that max(x, y) in the following expression (13) is a function to select “x” or “y”, whichever has a larger value.
log(e^x·e^y)=x+y  (12)
log(e^x+e^y)=max(x+y)  (13)

[0027] To simplify the description, the natural logarithm is represented by I, and the natural logarithms of the probabilities α_t, β_t and γ_t and soft-output λ_t are represented by Iα_t, Iβ_t, Iγ_t and Iλ_t, respectively, as shown in the following expression (14). Note that “sgn” in the expression (14) is a constant indicating a sign which provides a discrimination between positive and negative, that is, “+1” or “−1”.

[0028] $\begin{array}{cc}\{\begin{array}{c}\begin{array}{c}I{\alpha }_t\left(m\right)=\mathrm{sgn}·\log \left({\alpha }_t\left(m\right)\right)\\ I{\beta }_t\left(m\right)=\mathrm{sgn}·\log \left({\beta }_t\left(m\right)\right)\\ I{\gamma }_t\left(m\right)=\mathrm{sgn}·\log \left({\gamma }_t\left(m\right)\right)\end{array}\\ I{\lambda }_t=\mathrm{sgn}·\log {\lambda }_t\end{array}& \left(14\right)\end{array}$

[0029] The reason why such a constant sgn is given is that since each of the probabilities α_t, β_t and γ_t takes a value ranging from 0 to 1, each of the computed logarithmic likelihood Iα_t, Iβ_t and Iγ_t takes a negative value in principle.

[0030] For example, in case the decoder 1003 is constructed as a software, the constant sgn may be either “+1” or “−1” because the decoder 1003 can process any value, positive or negative. In case the decoder 1003 is constructed as a hardware, the positive/negative discrimination sign for a computed negative value should desirably be inverted and handled as a positive value in order to reduce the number of bits.

[0031] More particularly, in case the decoder 1003 is constructed as a system in which only negative values are handled as a log likelihood, the constant sgn takes “+1”. On the other hand, in case the decoder 1003 is constructed as a system in which only positive values are handled as a log likelihood, the constant sgn takes “−1”. In the following, the algorithms will be described with consideration given to the above.

[0032] In the Max-Log-BCJR algorithm, each of the log likelihood Iα_t, Iβ_t and Iγ_t is approximated as shown in the following expressions (15) to (17). The term “msgn(x, y)” in the expressions (15) and (16) indicates a function max(x, y) by which x or y, whichever has a larger value, is selected when the constant sgn is “+1”, while it indicates a function min(x, y) by which x or y, whichever is smaller in value, is selected when the constant sgn is “−1”. It is assumed here that the function msgn(x, y) in the state m′ at the right side of the expression (15) is determined within the state m′ in which there exists a transition to the state m, while the function msgn(x, y) in the state m′ at the right side of the expression (16) is determined within the state m′ in which there exists a transition from the state m.

[0033] $\begin{array}{cc}I{\alpha }_t\left(m\right)\simeq \underset{m^{\prime }}{\mathrm{msgn}}\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime }m\right)\right)& \left(15\right)\\ I{\beta }_t\left(m\right)\simeq \underset{m^{\prime }}{\mathrm{msgn}}\left(I{\beta }_{t+1}\left(m^{\prime }\right)+I{\gamma }_{t+1}\left(m,m^{\prime }\right)\right)& \left(16\right)\end{array}$
Iγ_t(m′,m)=sgn·(log(Pr{i_t=i(m′,m)})+log(Pr{y_t|x(m′,m)}))  (17)

[0034] With the Max-Log-BCJR algorithm, also the log soft-output Iλ_t is similarly approximated as given by the following expression (18). It is assumed here that the function msgn in the first term at the right side of the expression (18) is determined within the state m′ in which there exists a transition to the state m when the decoder 1003 is supplied with an input of “1”, while the function msgn in the second term is determined within the state m′ in which there exists a transition to the state m when the decoder 1003 is supplied with an input of “0”.

[0035] $\begin{array}{cc}I{\lambda }_{tj}\simeq \underset{\underset{i_j\left(m^{\prime },m\right)=1}{m^{\prime }m}}{\mathrm{msgn}}\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right)+I{\beta }_t\left(m\right)\right)-\underset{\underset{i_j\left(m^{\prime },m\right)=0}{m^{\prime }m}}{\mathrm{msgn}}\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right)+I{\beta }_t\left(m\right)\right)& \left(18\right)\end{array}$

[0036] Therefore, when making soft-output decoding with the Max-Log-BCJR algorithm, the decoder 1003 goes through a sequences of operational steps in a flow chart shown in FIG. 4 to determine a soft-output λ_t on the basis of the above relations.

[0037] First in step S1011 in FIG. 4, each time the decoder 1003 receives y_t, it computes log likelihood Iα_t(m) and Iλ_t(m′ m) on the basis of the above expressions (15) and (17).

[0038] Then in step S1012, after receiving all data in the sequence Y₁^T, the decoder 1003 computes a log likelihood Iβ_t(m) for each state m at all times t on the basis of the expression (16).

[0039] Then in step S1013, the decoder 1003 places, in the expression (18), the log likelihood Iα_t, Iβ_t and Iγ_t having been computed in steps S1011 and S1012 to compute a log soft-output Iλ_t at each time t.

[0040] Going through the above sequences of operational steps, the decoder 1003 can make the soft-output decoding with the Max-Log-BCJR algorithm.

[0041] Thus, since the Max-Log-BCJR algorithm includes no product operation, it permits to determine any desired value with considerably smaller amounts of computation than the BCJR algorithm.

[0042] Next, the Log-BCJR algorithm will be described. This algorithm is a version of the Max-Log-BCJR algorithm, which permits an approximation with a higher accuracy. More particularly, with the Log-BCJR algorithm, the probability sum operation shown in the expression (13) is deformed by adding a correction term as given by the following expression (19), to determine a correct log value by the sum operation. Such a correction will be called “log-sum correction”.
log(e^x+e^y)=max(x, y)+(1+e^−|x−y|)  (19)

[0043] The operation at the left side of the expression (19) will be called “log-sum operation”. According to the numeration system described in “Implementation and Performance of A Turbo/MAP Decoder” (S. S. Pietrobon; Int. J. Satellite Commun., vol. 16, pp. 23–46, January–February 1998), the operator for this log-sum operation will be denoted by “#” (which is “E” in the Pietrobon's paper) as in the following expression (20) for convenience' sake.
x#y=log(e^x+e^y)  (20)

[0044] Note that the expressions (19) and (20) are for the above constant sgn of “+1” but when the constant sgn is “−1”, operations corresponding to the expressions (19)and (20) are as given by the following expressions (21) and (22), respectively:
−log(e^−x+e^−y)=min(x, y)−log(1+e^−|x−y|)  (21)
x#y=−log(e^−x+e^−y)  (22)

[0045] Further, the operator for the cumulative add operation in the log-sum operation will be denoted by “#Σ” (which is “E” in the paper) as given by the following expression (23).

[0046] $\begin{array}{cc}\#\sum _{i=0}^{M-1}{x}_i=\left((\dots \left(\left(x_0\#x_1\right)\#x_2\right)\dots )\#x_{M-1}\right)& \left(23\right)\end{array}$

[0047] Using the above operators, the log likelihood Iα_t and Iβ_t and log soft-output Iλ_t in the Log-BCJR algorithm may be denoted as given by the following expressions (24) to (26), respectively. Note that since the log likelihood Iγ_t is denoted as given by the above expression (17), it will not be described.

[0048] $\begin{array}{cc}I{\alpha }_t\left(m\right)=\#\sum _{m^{\prime }=0}^{M-1}\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right)\right)& \left(24\right)\\ I{\beta }_t\left(m\right)=\#\sum _{m^{\prime }=0}^{M-1}\left(I{\beta }_{t+1}\left(m^{\prime }\right)+I{\gamma }_{t+1}\left(m,m^{\prime }\right)\right)& \left(25\right)\\ I{\lambda }_{\mathrm{tj}}=\#\sum _{i_j\left(\begin{array}{c}{m}^{\prime },m\\ m^{\prime },m\end{array}\right)=1}\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right)+I{\beta }_t\left(m\right)\right)-\#\sum _{i_j\left(\begin{array}{c}{m}^{\prime },m\\ m^{\prime },m\end{array}\right)=0}\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right)+I{\beta }_t\left(m\right)\right)& \left(26\right)\end{array}$

[0049] Note that the operator for the cumulative add operation in the log-sum operation in the state m′ at the right side of the above expression (24) will be determined in the state m′ in which there exists a transition to the state m and the operator for the cumulative add operation in the log-sum operation in the state m′ at the right side of the above expression (25) will be determined in the state m′ in which there exists a transition from the state m. Also, the operator for the cumulative add operation in the log-sum operation in the first term at the right side of the above expression (26) will be determined in the state m′ in which there exists a transition to the state m when the input is “1”, while the operator for the cumulative add operation in the log-sum operation in the second term will be determined in the state m′ in which there exists a transition to the state m when the input is “0”.

[0050] Therefore, when making soft-output decoding with the Log-BCJR algorithm, the decoder 1003 goes through the sequences of operational steps in the flow chart shown in FIG. 4 to determine a soft-output λ_t on the basis of the above relations.

[0051] First in step S1011 in FIG. 4, each time the decoder 1003 receives y_t, it computes log likelihood Iα_t(m) and Iγ_t(m′ m) based on the above expressions (24) and (17).

[0052] Then in step S1012, after receiving all data in the sequence Y₁^T, the decoder 1003 computes a log likelihood Iβ_t(m) for each state m at all times t based on the expression (25).

[0053] Then in step S1013, the decoder 1003 computes a log soft-output Iλ_t at each time t by placing, in the expression (26), the log likelihood Iα_t, Iβ_t and Iγ_t having been computed in steps S1011 and S1012.

[0054] Going through the above sequences of operational steps, the decoder 1003 can make the soft-output decoding with the Log-BCJR algorithm. Note that since in the above expressions (19) and (21), the correction term in the second term at the right side is represented by a one-dimensional function for a variable |x−y|, the decoder 1003 can accurately compute a probability by pre-storing the values of the corrective term as a table in a ROM (read-only memory) (not shown).

[0055] The Log-BCJR algorithm needs more operations than the Max-Log-BCJR algorithm but does not include any product operation, and its output except for a quantize error is the very log value of a BCJR algorithm soft-output.

[0056] It should be reminded that the BCJR algorithm, Max-Log-BCJR algorithm or Log-BCJR algorithm permitting to decode trellis codes such as convolutional code or the like may be used for decoding a code generated by using the trellis code as an element code and concatenating a plurality of element encoders via an interleaver. That is, the BCJR, Max-Log BCJR or Log-BCJR algorithm can be used for decoding a parallel concatenated convolutional codes (will be referred to as “PCCC” hereunder) or serially concatenated convolutional codes (will be referred to as “SCCC” hereunder), or turbo trellis-coded modulation (will be referred to as “TTCM” hereunder) or serial concatenated trellis-coded modulation (will be referred to as “SCTCM” hereunder), in which the PCCC or SCCC is combined with a multi-valued modulation and signal point mapping and error correction code decoding characteristic are collectively put in consideration.

[0057] A decoder to decode any of the above PCCC, SCCC, TTCM and SCTCM codes will make a so-called repetitive decoding by a plurality of element decoders each destined to make a maximum a posteriori probability (MAP) decoding based on the BCJR, Max-Log-BCJR or Log-BCJR algorithm.

[0058] It should be reminded that in case a code to be decoded is a punctured one or in a similar case, each of the element decoders has to be supplied with erasure position information, indicative of a position where there is not any coded output such as a puncture position or the like, as information necessary for the soft-output decoding. The erasure position information has to be held separately at least until a log likelihood Iγ is computed. To this end, each of the decoders should be provided with a memory circuit to hold the erasure position information, for example, which has been a cause of an increased circuit scale.

[0059] Decoding of a code whose parallel paths exist in a trellis will be discussed herebelow. In this case, though the parallel paths can be regarded as a single path because its transition origins are same in state and transition destinations are also same in state, each element decoder has to decode the parallel paths as two paths. Especially when computing log likelihood Iα and Iβ, a larger number of paths have to be considered, and so the processing burden to each of the element decoders will be larger.

[0060] Also, when computing a log soft-output Iλ, each element decoder has to predetermine the sum of log likelihood Iα and Iλ. Namely, to compute the log soft-output Iλ, each element decoder should normally be provided with a separate circuit to compute the sum of log likelihood Iα and Iγ. Thus, in each of the element decoders, the circuit to compute the log soft-output Iλ will possibly be increased in scale.

[0061] To overcome the above-mentioned drawbacks of the prior art, the present invention has an object to provide a soft-output decoding apparatus and method, capable of representing a code erasure position by a small-scale, simple-structured circuit. The present invention has another object to provide a decoding apparatus and method, suitable for repetitive decoding by which a code erasure position can be expressed by a small-scale, simple-structured circuit.

[0062] The present invention has another object to provide a soft-output decoding apparatus and method, capable of soft-output decoding with less operating burden, with no degradation of processing performance and at a high operating speed. The present invention has another object to provide a decoding apparatus and method, suitable for repetitive decoding, by which a soft-output can be decoded with less processing burden, with no degradation of processing performance and at a high operating speed.

[0063] The present invention has another object to provide a soft-output decoding apparatus and method, capable of soft-output decoding by a small-scale, simple-structured circuit. The present invention has another object to provide a decoding apparatus and method, suitable for repetitive decoding by which a soft-output can be decoded by a small-scale, simple-structured circuit.

[0064] The above object can be attained by providing a soft-output decoder which determines, based on a received value taken as a soft-input, a log likelihood logarithmically notated of a probability of passing through arbitrary states and makes decoding with the log likelihood, the apparatus including a zero-symbol replacing means for replacing a position where no coded output exists with a symbol whose likelihood is “0”, based on erasure position information indicative of an erasure position of the coded output, and a soft-output decoding means which is supplied with the received value and a priori probability information, and makes soft-output decoding of the data to generate a log soft-output logarithmically notated of a soft-output at each time and/or extrinsic information. Also, the above object can be attained by providing a soft-output decoding method.

[0065] Also, the above object can be attained by providing a soft-output decoder which determines, based on a received value taken as a soft-input, a log likelihood logarithmically notated of a probability of passing through arbitrary states and makes decoding with the log likelihood, the apparatus including a first probability computing means for computing, for each received value, a first log likelihood logarithmically notated of a first probability determined based on an output pattern of a code and received value, a first probability distributing means for distributing the first log likelihood so as to correspond to each branch of a trellis corresponding to the configuration of the code, and a parallel path processing means for tying together the first log likelihood corresponding to the first parallel paths when the code to be decoded includes parallel paths whose transition origins are same in state and transition destinations are same in state. Also, the above object can be attained by providing a soft-output decoding method.

[0066] Also, the above object can be attained by providing a soft-output decoder which determines, based on a received value taken as a soft-input, a log likelihood logarithmically notated of a probability of passing through arbitrary states and makes decoding with the log likelihood, the apparatus including a first probability computing means for computing, for each received value, a first log likelihood logarithmically notated of a first probability determined based on the output pattern of a code and the received value, a second probability computing means for computing, for each received value, a second log likelihood logarithmically notated of a second probability of transition from a coding start state to each state in time sequence on the basis of the first log likelihood, a third probability computing means for computing, for each received value, a third log likelihood logarithmically notated of a third probability of transition from a coding termination state to each state in reverse time sequence on the basis of the first log likelihood, and a soft-output computing means for computing a log soft-output logarithmically notated of a soft-output at each time on the basis of the first to third log likelihood, the second probability computing means supplying the soft-output computing means with the sum of the second log likelihood and the first log likelihood determined in the process of computing the second log likelihood. Also, the above object can be attained by providing a soft-output decoding method.

[0188] Referring to the drawings, preferred embodiments of the present invention will be explained in detail.

[0189] FIG. 5 is a block diagram of a communication model adopting the data transmission/reception system as one embodiment of the present invention. As shown, digital information is coded by an encoder 1 included in a transmitter (not shown), output from the encoder 1 is supplied to a receiver (not shown) via a noisy non-storage channel 2, and the coded digital information is decoded by a decoder 3 included in the receiver.

[0190] In this data transmission/reception system, the encoder 1 is designed to code the digital information by the parallel concatenated convolutional coding (will be referred to as “PCCC” hereunder) or serially concatenated convolutional coding (will be referred to as “SCCC” hereunder), in which trellis codes such a convolutional code are used as element codes, or turbo trellis-coded modulation (will be referred to as “TTCM” hereunder) or serial concatenated trellis-coded modulation (will be referred to as “SCTCM” hereunder), in which the PCCC or SCCC is combined with a multi-valued modulation. These types of coding are known as a so-called turbo coding.

[0191] On the other hand, the decoder 3 is provided to decode a code from the encoder 1. It is formed from a plurality of concatenated element decoders to make a so-called repetitive decoding. Each of these element decoders is a module including at least an interleaver to relocate input data and a soft-output decoder which makes a maximum a posteriori probability (MAP) decoding based on the Max-Log-MAP or Log-Map algorithm (will be referred to as “Max-Log-BCJR algorithm” and “Log-MCJR algorithm”, respectively, hereunder) proposed by Robertson, Villebrun and Hoeher in their “A Comparison of Optimal and Sub-optimal MAP Decoding Algorithms Operating in the Domain” (IEEE Int. Conf. on Communications, pp. 1009–1013, June 1995) to provide a log soft-output Iλ corresponding to log likelihood Iα, Iβ and Iγ and so-called a posteriori probability information, logarithmically notated in the form of log likelihood by natural logarithms, respectively, of so-called probabilities α, β and γ and soft-output λ.

[0192] More particularly, the decoder 3 has a function to make a choice between a received value supplied to each of the element decoders and a so-called extrinsic information, as a code likelihood, and thus can appropriately select input information for soft-output decoding and decode a desired one of PCCC, SCCC, TTCM and SCTCM codes without changing the circuit construction.

[0193] Note that in the following, each of the element decoders in the decoder 3 will be described as a one destined to make MAP decoding based on the Log-BCJR algorithm.

[0194] The present invention will further be described sequentially in the order of the following contents of the description:

[0195] Contents:

• • [0196] 1. Overview of encoder and decoder for coding and decoding, respectively, based on PCCC, SCCC, TTCM or SCTCM
    • [0197] 1.1 Encoder and decoder for PCCC-based coding and decoding
    • [0198] 1.2 Encoder and decoder for SCCC-based coding and decoding
  • [0199] 2. Detailed description of element decoder
    • [0200] 2.1 General construction of element decoder
    • [0201] 2.2 Detailed description of soft-output decoding circuit
    • [0202] 2.3 Detailed description of interleaver
  • [0203] 3. Decoder formed from concatenated element decoders
  • [0204] 4. Functions of all element decoders
    • [0205] 4.1 Switching code likelihood
    • [0206] 4.2 Delaying received value
    • [0207] 4.3 Selecting received value to be decoded
    • [0208] 4.4 Using decoding and delaying-use data storage circuits in common
    • [0209] 4.5 Delaying frame-top information
    • [0210] 4.6 Operation of soft-output decoding circuit or interleaver as unit
    • [0211] 4.7 Switching delay mode
    • [0212] 4.8 Generating next-stage information
    • [0213] 4.9 System check
  • [0214] 5. Functions of soft-output decoding circuit
    • [0215] 5.1 Supplying code information
      • [0216] 5.1.1 Computing input/output patterns for all trellis branches
      • [0217] 5.1.2 Numbering between transition origins and destination states
      • [0218] 5.1.3 Numbering along time base, and numbering in sequence opposite to time base
      • [0219] 5.1.4 Numbering based on uniqueness of entire trellis
    • [0220] 5.2 Entering termination information
      • [0221] 5.2.1 Entering information for input bits for termination period
      • [0222] 5.2.2 Entering information indicative of termination state for one time slot
    • [0223] 5.3 Processing of erasure position
    • [0224] 5.4 Computing and distributing log likelihood Iγ
      • [0225] 5.4.1 Computing and distributing log likelihood Iγ for all input/output patterns
      • [0226] 5.4.2 Computing and distributing log likelihood Iγ for at least a part of the input/output patterns
      • [0227] 5.4.3 Normalizing log likelihood Iγ for all input/output patterns at each time
      • [0228] 5.4.4 Normalizing log likelihood Iγ for at least a part of the input/output patterns
    • [0229] 5.5 Computing log likelihood Iα and Iβ
      • [0230] 5.5.1 Computing sum of log likelihood Iα and Iγ
      • [0231] 5.5.2 Pre-processing parallel paths
      • [0232] 5.5.3 Sharing add/compare selection circuit for different codes
      • [0233] 5.5.4 Outputting log likelihood Iγ for computation of log soft-output Iγ
      • [0234] 5.5.5 Computing sum of log likelihood Iα and Iγ for parallel paths
      • [0235] 5.5.6 Selecting log likelihood corresponding to code configuration
      • [0236] 5.5.7 Normalizing log likelihood Iα and Iβ
      • [0237] 5.5.8 Computing correction term in the log-sum correction
      • [0238] 5.5.9 Generating selection-use control signal in log-sum operation
    • [0239] 5.6 Computing log soft-output Iλ
      • [0240] 5.6.1 Cumulative add operation in log-sum operation with enable signal
      • [0241] 5.6.2 Cumulative add operation in log-sum operation without enable signal
    • [0242] 5.7 Normalizing extrinsic information
    • [0243] 5.8 Hard decision of received value
  • [0244] 6. Functions of interleaver
    • [0245] 6.1 Plural kinds of interleaving functions
    • [0246] 6.2 Using interleaving-use and delaying-use data storage circuits in common
    • [0247] 6.3 Controlling operation of storage circuit with clock inhibit signal
    • [0248] 6.4 De-interleaving
    • [0249] 6.5 Generating write and read addresses
    • [0250] 6.6 Delaying for length of interleaving
    • [0251] 6.7 Utilizing address space
    • [0252] 6.8 Writing and reading data by partial-write function
    • [0253] 6.9 Providing both even-length delay and odd-length delay
    • [0254] 6.10 Changing input/output sequence
  • [0255] 7. Conclusion

[0256] 1. Overview of Encoder and Decoder for Coding and Decoding, Respectively, Based on PCCC, SCCC, TTCM or SCTCM

[0257] Prior to starting the detailed description of the present invention, there will first be described an encoder 1′ and decoder 3′ for the PCCC-based coding and decoding, respectively, shown in FIGS. 6 and 7, and an encoder 1″ and decoder 3″ for the SCCC-based coding and decoding, respectively, shown in FIGS. 8 and 9, in order to make clear the extension of the present invention. The encoders 1′ and 1″ are examples of the aforementioned conventional encoder 1, and the decoders 3′ and 3″ are examples of the aforementioned conventional decoder 3. Each of the decoders 3′ and 3″ is formed from concatenated element decoders.

[0258] 1.1 Encoder and Decoder for the PCCC-Based Coding and Decoding

[0259] First, there will be described the encoder 1′ to decode digital information based on the PCCC algorithm and the decoder 3′ to decode the code from the encoder 1′.

[0260] Some of the encoders 1′ include a delayer 11 to delay input data, two convolutional encoders 12 and 14, and an interleaver 13 to arrange the input data in a difference sequence, as shown in FIG. 6. The encoder 1′ makes a “⅓” parallel concatenated convolutional coding of 1-bit input data D1 to generate 3-bit output data D4, D5 and D6 and outputs them to outside via a modulator which adopts for example the binary-phase shift keying (will be referred to as “BPSK” hereunder) or quadrature-phase shift keying (will be referred to as “QPSK” hereunder). The modulator is not illustrated.

[0261] The delayer 11 is provided to time outputting of the 3-bit output data D4, D5 and D6. Receiving the 1-bit input data D1, the delayer 11 delays the input data D1 the same time as taken by the interleaver 13 for its operation. The delayer 11 outputs delayed data D2 provided as a result of the delaying of the input data D1 as an output data D4 to outside, while supplying it to the downstream convolutional encoder 12.

[0262] Receiving the 1-bit delayed data D2 from the delayer 11, the convolutional encoder 12 makes convolution of the delayed data D2, and outputs the result of operation as an output data D5 to outside.

[0263] The interleaver 13 is supplied with the 1-bit input data D1, arranges, in a difference sequence, the bits forming together the input data D1 to generate interleaved data D3, and supplies the thus generated data D3 to a downstream convolutional encoder 14.

[0264] Receiving the 1-bit interleaved data D3 supplied from the interleaver 13, the convolutional encoder 14 makes convolution of the interleaved data D3, and outputs the result of operation as an output data D6 to outside.

[0265] Supplied with the 1-bit input data D1, the encoder 1′ outputs it as an component output data D4 as it is to outside via the delayer 11, and outputs, to outside, the output data D5 provided as a result of the convolution of delayed data D2 by the convolutional encoder 12 and output data D6 provided as a result of the convolution of interleaved data D3 by the convolutional encoder 14, thereby making parallel concatenated convolutional coding at a total rate of “⅓”. The data coded by the encoder 1′ is subjected to signal point mapping by a modulator (not shown) in a predetermined way of modulation, and outputted to a receiver via the non-storage channel 2.

[0266] On the other hand, some of the decoders 3′ to decode the data from the encoder 1′ include two soft-output decoding circuits 15 and 17, an interleaver 16 to alter the sequence of input data, two de-interleavers 18 and 20 to restore the sequence of the input data to the initial one, and two adders 19 to add two data together, as shown in FIG. 7. The decoder 3′ estimates the input data D1 in the encoder 1′ from received value D7 made as a soft-input under the influence of a noise developed in the non-storage channel 2, and outputs it as decoded data D13.

[0267] The soft-output decoding circuit 15 is provided correspondingly to the convolutional encoder 12 in the encoder 1′ to make MAP decoding based on the Log-BCJR algorithm. The soft-output decoding circuit 15 is supplied with a received value D7 of the soft-input and a priori probability information D8 for information bits of soft-input from the de-interleaver 18, and uses the received value D7 and a priori probability information D8 for the soft-output decoding. The soft-output decoding circuit 15 thus generates extrinsic information D9 for information bits obtained under code binding conditions, and outputs the extrinsic information D9 as a soft-output to the downstream interleaver 16.

[0268] The interleaver 16 is provided to interleave the extrinsic information D9 for the information bits being the soft-output from the soft-output decoding circuit 15 based on the same replacement position information as in the interleaver 13 in the encoder 1′. The interleaves 16 outputs the data provided as the result of interleaving as a priori probability information D10 for information bits in the downstream soft-output decoding circuit 17, while outputting it to the downstream adder 19.

[0269] The soft-output decoding circuit 17 is provided correspondingly to the convolutional encoder 14 in the encoder 1′ to make MAP decoding based on the Log-BCJR algorithm as in the soft-output decoding circuit 15. The soft-output decoding circuit 17 is supplied with the received value D7 of the soft-input and a priori probability information D10 for the information bits of the soft-input from the interleaver 16, and makes soft-output decoding with the received value D7 and a priori probability information D10. Thus, the soft-output decoding circuit 17 generates extrinsic information D11 for information bits obtained under code-binding conditions, and outputs it as a soft-output to the de-interleaver 18, while outputting it to the adder 19.

[0270] The de-interleaver 18 is provided to de-interleave the extrinsic information D11 of the soft-input from the soft-output decoding circuit 17 to restore the bit sequence of the interleaved data D3 interleaved by the interleaver 13 in the encoder 1′ to that of the initial input data D1. The de-interleaver 18 outputs the data provided by the de-interleaving as the a priori probability information D8 for the information bits in the soft-output decoding circuit 15.

[0271] The adder 19 is provided to add together the a priori probability information D10 for the information bits of the soft-input from the interleaver 16 and extrinsic information D11 for the information bits from the soft-output decoding circuit 17. The adder 19 outputs the thus obtained data D12 as a soft-output to the downstream de-interleaver 20.

[0272] The de-interleaver 20 is provided to de-interleave the soft-output data D12 from the adder 19 to restore the bit sequence of the interleaved data D3 interleaved by the interleaver 13 in the encoder 1′ to that of the initial input data D1. The de-interleaver 20 outputs the data provided by the de-interleaving as the decoded data D13 to outside.

[0273] Since the decoder 3′ is provided with the soft-output decoding circuits 15 and 17 corresponding to the convolutional encoders 12 and 14, respectively, provided in the encoder 1′, so a code whose decoding complexity is high can be decomposed to elements whose decoding complexity is low to sequentially improve the characteristic under the interaction between the soft-output decoding circuits 15 and 17. Receiving the received value D7, the decoder 3′ makes repetitive decoding a predetermined number of times, and outputs the decoded data D13 based on the extrinsic information of the soft-output obtained as the result of the decoding.

[0274] Note that an encoder for TTCM-based coding can be implemented by providing, at the last stage of the encoder 1′, a modulator for 8-phase shift keying (will be referred to as “8PSK” hereunder) modulation, for example. Also note that a decoder for TTCM-based decoding can be implemented by designing it similarly to the decoder 3′ and symbols of common-phase and orthogonal components as received values will be supplied directly to the decoder.

[0275] 1.2 Encoder and Decoder for the SCCC-Based Coding and Decoding

[0276] Next, there will be described the encoder 1″ to make SCCC-based coding and the decoder 3″ to decode the code from the encoder 1″.

[0277] Some of the encoders 1″ include a convolutional encoder 31 to code a code called “outer code”, an interleaver 32 to arrange input data in a difference sequence, and a convolutional encoder 33 to encode a code called “inner code”, as shown in FIG. 8. The encoder 1″ makes serially concatenated convolution at a rate of “⅓” for coding of 1-bit input data D21 to generate 3-bit output data D26, D27 and D28, and outputs them to outside via a BPSK- or QPSK-based modulator (not shown), for example.

[0278] Supplied with the 1-bit input data D21, the convolutional encoder 31 makes a convolution of the input data D21, and supplies the result of convolution as 2-bit coded data D22 and D23 to the downstream interleaver 32. More particularly, the convolutional encoder 31 makes convolution at a rate of “½” for coding an outer code, and supplies the thus generated data D22 and D23 to the downstream interleaver 32.

[0279] The interleaver 32 is supplied with the coded data D22 and D23 of two bit sequences from the convolutional encoder 31, arranges, in a different sequence, bits forming together the coded data D22 and D23, and supplies interleaved data D24 and D25 of the two generated bit sequences to the downstream convolutional encoder 33.

[0280] The convolutional encoder 33 is supplied with the 2-bit interleaved data D24 and D25 from the interleaver 32, makes convolution of these interleaved data D24 and D25, and outputs the result of convolution as 3-bit output data D26, D27 and D28 to outside. More particularly, the convolutional encoder 33 makes convolution at a rate of “⅔” for coding an inner code, and outputs the output data D26, D27 and D28 to outside.

[0281] The encoder 1″ makes a convolution of “½” in rate for coding an outer code by the convolutional encoder 31 and a convolution of “⅔” in rate for coding an inner code by the convolutional encoder 33, thereby making serially concatenated convolution at a total rate of “(½)×(⅔)=⅓”. The data coded by the encoder 1″ is subjected to signal point mapping by a modulator (not shown) in a predetermined way of modulation, and outputted to a receiver via the non-storage channel 2.

[0282] On the other hand, some of the decoders 3″ to decode data from the encoder 1″ include two soft-output decoding circuits 34 and 36, a de-interleaver 35 to restore the sequence of input data to the initial one, and an interleaver 37 to rearrange the input data, as shown in FIG. 9. The decoder 3″ estimates input data D21 to the encoder 1″ from a received value D29 made as a soft-input under the influence of a noise developed in the non-storage channel 2, and outputs it as decoded data D36.

[0283] The soft-output decoding circuit 34 is provided correspondingly to the convolutional encoder 33 in the encoder 1″ to make MAP decoding based on the Log-BCJR algorithm. The soft-output decoding circuit 34 is supplied with the soft-input received value D29 as well as with a priori probability information D30 for information bits of the soft-input from the interleaver 37, uses the received value D29 and a priori probability information D30 to make soft-output decoding of an inner code by making the MAP decoding based on the Log-BCJR algorithm. The soft-output decoding circuit 34 generates extrinsic information D31 for information bits determined under code-binding conditions, and outputs the extrinsic information D31 as soft-output to the downstream de-interleaver 35. Note that the extrinsic information D31 corresponds to the interleaved data D24 and D25 from the interleaver 32 in the encoder 1″.

[0284] The de-interleaver 35 is provided to de-interleave the extrinsic information D31 of the soft-input from the soft-output decoding circuit 34 to restore the bit sequence of the interleaved data D24 and D25 from the interleaver 32 in the encoder 1″ to that of the initial input data D22 and 23. The de-interleaver 35 outputs the data provided by the de-interleaving as the a priori probability information D32 for the code bits in the downstream soft-output decoding circuit 36.

[0285] The soft-output decoding circuit 36 is provided correspondingly to the convolutional encoder 31 in the encoder 1″ to make MAP decoding based on the Log-BCJR algorithm. The soft-output decoding circuit 36 is supplied with the a priori probability information D32 for code bits of the soft-input from the de-interleaver 35 as well as with the a priori probability information D33 for information bits whose value is “0”, and uses these a priori probability information D32 and D33 to make the MAP decoding based on the Log-BCJR algorithm for soft-output decoding of an outer code. The soft-output decoding circuit 36 generates the extrinsic information D34 and D35 determined under the code-binding conditions and outputs the extrinsic information D34 as decoded data D36 to outside and the extrinsic information D35 as soft-output to the interleaver 37.

[0286] The interleaver 37 is provided to interleave the extrinsic information D35 for the information bits being the soft-output from the soft-output decoding circuit 36 based on the same replacement position information as in the interleaver 32 in the encoder 1″. The interleaver 37 outputs the data provided as the result of interleaving as a priori probability information D30 for information bits in the soft-output decoding circuit 34.

[0287] Since the decoder 3″ is provided with the soft-output decoding circuits 36 and 34 corresponding to the convolutional encoders 31 and 33, respectively, provided in the encoder 1″, so a code whose decoding complexity is high can be decomposed to elements whose decoding complexity is low as in the decoder 3′ to sequentially improve the characteristic under the interaction between the soft-output decoding circuits 34 and 36. Receiving the received value D29, the decoder 3″ makes the repetitive decoding a predetermined number of times, and outputs the decoded data D36 based on the extrinsic information of the soft-output obtained as the result of decoding.

[0288] Note that an encoder for SCTCM-based coding can be implemented by providing a modulator for the 8PSK modulation, for example, at the last stage of the encoder 1″. Also note that a decoder for SCTCM-based decoding can be implemented by designing it similarly to the decoder 3″ and symbols of common-phase and orthogonal components as received values will be directly supplied to the decoder.

[0289] 2. Detailed Description of the Element Decoder

[0290] In the decoder 3 as the embodiment of the present invention, a plurality of element decoders, each including a module comprised of at least a soft-output decoding circuit and an interleaver or de-interleaver, is concatenated to each other, as shown by a dash-line block in FIG. 7 or 9, to decode any of PCCC, SCCC, TTCM or SCTCM codes. Since the de-interleaver is to rearrange, according to the inverse replacement position information, data into a sequence opposite to that in the interleaver, it may be regarded as a version of the interleaver. Thus, the element decoder may be a one including a soft-output decoding circuit and interleaver. Namely, the interleaver may be used as switched for either the interleaving or de-interleaving function. In the following, the interleaver will be described as a one having also the de-interleaving function wherever no differentiation between the interleaver and de-interleaver is required.

[0291] The element decoders provided in the decoder 3 will be described in detail below. Note that a number M of states (transition state) indicating a content of the shift register provided in each element encoder in the encoder 1 will be denoted by m(0, 1, . . . , M-1), respectively, as necessary and the state at a time t will be denoted by S_t. On the assumption that information of k bits is inputted in one time slot, input at the time t is denoted by i_t=(i_t1, i_t2, . . . , i_tk) and input system is by I₁^T=(i₁, i₂, . . . , i_T). In case a transition takes place from a state m′ to a state m, information bit corresponding to the transition is denoted by i(m′, m)=(i₁(m′, m), i₂(m′, m), . . . , i_k(m′, m)). Further, on the assumption that an n-bit code is outputted in one time slot, output at the time t is denoted by X_t=(x_t1, x_t2, . . . , x_tn) and output system is by X₁^T=(X₁, X₂, . . . , X_T). In case a transition occurs from the state m′ to m, code bit corresponding to the transition is denoted by X(m′, m)=(x₁(m′, m), x₂ (m′, m), . . . , x_n(m′, m)). The non-storage channel 2 is assumed to output Y₁^T when having been supplied with X₁^T. On the assumption that n-bit received value is outputted in one time slot, output at the time t is denoted by y_t=(y_t1, y_t2, . . . , y_tn) and Y₁^T=(y₁, y₂, . . . , y_T).

[0292] 2.1 General Construction of the Element Decoder

[0293] The element decoder as a whole will be described herebelow with reference to FIGS. 10 to 12.

[0294] FIG. 10 schematically illustrates an element decoder indicated with a reference 50. It is built in the form of a one-chip, as a large-scale integrated circuit (will be referred to as “LSI” hereunder), having the following elements formed integrally on a single semiconductor substrate. As shown, the element decoder 50 includes a control circuit 60 to control all the other elements, a to-be-decoded received value selection circuit 70 to select a received value to be decoded, an edge detection circuit 80 to detect a frame top, a soft-output decoding circuit 90, an interleaver 100 to alter the sequence of input data, an address storage circuit 110 to hold a replacement-destination address data to which the interleaver 100 makes reference, ten selectors 120₁, 120₂, 120₃, 120₄, 120₅, 120₆, 120₇, 120₈, 120₉ and 120₁₀, and a signal line 130 used for system check.

[0295] The left half of the element decoder 50 in FIG. 10 is detailed in FIG. 11, while the right half is detailed in FIG. 12.

[0296] The control circuit 60 generates and supplies various kinds of information to each of the to-be-decoded received value selection circuit 70, soft-output decoding circuit 90, interleaver 100, address storage circuit 110 and nine selectors 120₂, 120₃, 120₄, 120₅, 120₆, 120₇, 120₈, 120₉ and 120₁₀ and receives information from the address storage circuit 110 to control the operation of each of the elements.

[0297] More particularly, the control circuit 60 generates and supplies, to the to-be-decoded received value selection circuit 70, received value selection information CRS under which a to-be-decoded received value TSR is selected from the received value R (received value TR).

[0298] Also, the control circuit 60 generates and supplies, to the soft-output decoding circuit 90, received value format information CRTY indicating the format of the received value R which indicates whether data supplied as the received value R is actually a received value or extrinsic information or an I/Q value in case the encoder 1 is for the TTCM or SCTCM coding; a priori probability information format information CAPP indicating the format of a priori probability information which indicates whether the a priori probability information is supplied bit by bit or symbol by symbol; rate information CRAT indicating the rate of the element encoder in the encoder 1; generator matrix information CG indicating the generator matrix of the element encoder in the encoder 1; and signal point mapping information CSIG in case the encoder 1 is for the TTCM or SCTCM coding.

[0299] Also, the control circuit 60 generates and supplies, to the interleaver 100, interleaver type information CINT indicating the type of an interleaving to be done; interleaving length information CINL; interleaver input/output replacement information CIPT about the operation of the interleaver 100 such as input/output replacement information for a mutual replacement in sequence between a plurality of symbols as will be described in detail later; code termination position information CNFT; code termination period information CNFL; code termination state information CNFD; puncture period information CNEL indicating a puncture period in case a code has been punctured; and puncture pattern information CNEP. Also, the control circuit 60 generates and supplies operation mode information CBF indicating an operation mode which will be described in detail later to the interleaver 100.

[0300] Also, in case the replacement-destination address data to which the interleaver 100 makes reference is written to the address storage circuit 110, the control circuit 60 supplies the address storage circuit 110 with the interleaver type information CINT, address CIAD indicating the address of the address storage circuit 110, and a write data CIWD being the replacement-destination address data to which the interleaver 100 makes reference.

[0301] Also, the control circuit 60 supplies the operation mode information CBF to the six selectors 120₂, 120₃, 120₄, 120₅, 120₆ and 120₇, while supplying three selectors 120₈, 120₉ and 120₁₀ with check mode information CTHR.

[0302] On the other hand, the control circuit 60 is supplied with read address data ADA being the replacement-destination address data held in the address storage circuit 110 and to which the interleaver 100 makes reference.

[0303] The control circuit 60 supplies the various kinds of information thus generated to the to-be-decoded received value selection circuit 70, soft-output decoding circuit 90, interleaver 100 and 120₂, 120₃, 120₄, 120₅, 120₆, 120₇, 120₈, 120₉ and 120₁₀ to control the operations of these elements, and controls the write of address data to the address storage circuit 110.

[0304] The to-be-decoded received value selection circuit 70 is provided to decode an arbitrary code as will be described in detail later. Based on the received value selection information CRS supplied from the control circuit 60, the to-be-decoded received value selection circuit 70 selects a to-be-decoded received value TSR of the input received value TR. It supplies the selected to-be-decoded received value TSR to the soft-output decoding circuit 90.

[0305] More particularly, on the assumption that the received value TR consists of six sequences of received values TR0, TR1, TR2, TR3, TR4 and TR5, for example, and four of the sequences are selected as to-be-decoded received values TSR0, TSR1, TSR2 and TSR3), the to-be-decoded received value selection circuit 70 can be implemented as a one having four selectors 71, 72, 73 and 74 as shown in FIG. 13 for example. At this time, the received value selection information CRS supplied from the control circuit 60 is supplied to each of the selectors 71, 72, 73 and 74, and it is composed of four sequences of received value selection information CRS0, CRS1, CRS2 and CRS3.

[0306] That is, the selector 71 selects a predetermined one of the TR0, TR1, TR2, TR3, TR4 and TR5 on the basis of the received value selection information CRS0, and supplies it as a to-be-decoded received value TSR0 to the soft-output decoding circuit 90.

[0307] Also, the selector 72 selects a predetermined one of the TR0, TR1, TR2, TR3, TR4 and TR5 on the basis of the received value selection information CRS1, and supplies it as a to-be-decoded received value TSR1 to the soft-output decoding circuit 90.

[0308] Also, the selector 73 selects a predetermined one of the TR0, TR1, TR2, TR3, TR4 and TR5 on the basis of the received value selection information CRS2, and supplies it as a to-be-decoded received value TSR2 to the soft-output decoding circuit 90.

[0309] Also, the selector 74 selects a predetermined one of the TR0, TR1, TR2, TR3, TR4 and TR5 on the basis of the received value selection information CRS3, and supplies it as a to-be-decoded received value TSR3 to the soft-output decoding circuit 90.

[0310] Thus, the to-be-decoded received value selection circuit 70 selects the to-be-decoded received value TSR on the basis of the received value selection information CRS supplied from the control circuit 60, and supplies it to the soft-output decoding circuit 90.

[0311] The edge detection circuit 80 is supplied with an external interleave start position signal ILS (interleave start position signal TILS) indicating an interleave start position, namely, a frame top, to detect the top of a frame forming an input received value TR. The edge detection circuit 80 supplies the soft-output decoding circuit 90 and selector 120₅ with an edge signal TEILS indicating the top of the detected frame.

[0312] More specifically, the edge detection circuit 80 can be implemented as a one having a register 81 and AND gate 82 as shown in FIG. 14 for example.

[0313] The register 81 holds a 1-bit interleave start position signal TILS for example for one clock only. The register 81 supplies the held interleave start position, that is, a delayed interleave start position signal TILSD to the AND gate 82.

[0314] The AND gate 82 carries out the logical AND between the interleave start position signal TILS and a data resulting from inversion of the delayed interleave start position signal TILSD supplied from the register 81 and which is an interleave start position signal TILS one clock before the signal TILSD. The AND gate 82 supplies the thus obtained logical product or AND as an edge signal TEILS to the soft-output decoding circuit 90 and selector 120₅.

[0315] Namely, the edge detection circuit 80 should detect when the interleave start position signal TILS supplied from outside for example is switched from “0” to “1”. By AND operation by the AND gate 82, it can detect that the top of a frame forming a received value TR has been entered.

[0316] The soft-output decoding circuit 90 uses a to-be-decoded received value TSR supplied from the to-be-decoded received value selection circuit 70 and extrinsic information supplied as a priori probability information from outside or interleaved data EXT (extrinsic information or interleaved data TEXT) to make an MAP decoding based on the Log-BCJR algorithm.

[0317] At this time, the soft-output decoding circuit 90 makes a decoding operation with a received value type information CRTY, a priori probability information type information CAPP, rate information CRAT, generator matrix information CG and signal point mapping information CSIG (if necessary) supplied from the control circuit 60, erasure information ERS (erasure information TERS) indicating a puncture pattern and a priori probability information erasure information EAP (a priori probability information erasure information TEAP) supplied from outside, termination time information TNP (termination time information TTNP) indicating a code termination time, and termination state information TNS (termination state information TTNS) indicating a termination state.

[0318] The soft-output decoding circuit 90 supplies the selector 120₁ with a soft-output SOL and extrinsic information SOE, obtained as the result of decoding. At this time, the soft-output decoding circuit 90 selectively outputs information about information symbols or information bits and information about code symbols or code bits on the basis of an output data selection control signal ITM (output data selection control signal CITM) supplied from outside. Also, in case a hard decision has been made, the soft-output decoding circuit 90 outputs, to outside, decoded value hard decision information SDH obtained via hard decision of a soft-output being a decoded value and received value hard decision information SRH obtained via hard decision of a received value. Also in this case, the soft-output decoding circuit 90 selectively outputs information about information symbols or information bits and information about code symbols or code bits on the basis of the output data selection control signal CITM.

[0319] Also, the soft-output decoding circuit 90 can delay the received value TR, extrinsic information or interleaved data TEXT, and the edge signal TEILS supplied from the edge detection circuit 80 as will be described in detail later. In this case, the soft-output decoding circuit 90 supplies the delayed received value SDR resulted from delaying of the received value TR to the selectors 120₃ and 120₆, delayed extrinsic information SDEX resulted from delaying of the extrinsic information or interleaved data TEXT to the select 120₂, and delayed edge signal SDILS resulted from delaying of the edge signal TEILS to the selector 120₅.

[0320] Note that the soft-output decoding circuit 90 will be described in detail in Subsection 2.2.

[0321] The interleaver 100 interleaves the data TII supplied from the selector 120₄ on the basis of the same replacement position information as that in the interleaver (not shown) in the encoder 1 or de-interleaves the data TII to restore the bit mapping of the interleaved data from the interleaver in the encoder 1 to that of the initial data. At this time, the interleaver 100 works as an interleaver or de-interleaver according to the interleave mode signal DIN (interleave mode signal CDIN) supplied from outside.

[0322] Supplied with the interleave start position signal TIS from the selector 120₅, the interleaver 100 addresses by supplying address data IAA to the address storage circuit 110 to read an address data held in the address storage circuit 110 as reading address data ADA and make an interleaving or de-interleaving based on the reading address data ADA. At this time, the interleaver 100 uses the interleaver type information CINT, interleaving length information CTNL and interleaver input/output replacement information CIPT supplied from the control circuit 60 to make an interleaving or de-interleaving. The interleaver 100 supplies interleaver output data IIO obtained via the interleaving or de-interleaving to the selector 120₇.

[0323] Also, the interleaver 100 can delay the data TDI about the received value TR or delayed received value SDR supplied from the selector 120₃ as will be described in detail later. At this time, the interleaver 100 delays the data TDI on the basis of the operation mode information CBF supplied from the control circuit 60. The interleaver 100 supplies the selector 120₆ with the interleaving length delay information IDO obtained via delaying the data TDI.

[0324] Further, in case the decoder is formed from a plurality of element decoders concatenated to each other, the interleaver 100 is supplied with the termination position information CNFT, termination period information CNFL, termination state information CNFD, puncture period information CNEL and puncture pattern information CEP supplied from the control circuit 60 to generate termination time information IGT and termination state information IGS, indicating the termination time and termination state of a code in the next-state element decoder, and erase position information IGE and interleaver no-output position information INO, indicating a punctured position of the code, on the basis of the supplied pieces of information. At the same time, the interleaver 100 delays the interleave start position information TIS supplied from the selector 120₅ to generate delayed interleave start position signal IDS. The interleaver 100 supplies the selector 120₁₀ with the thus generated termination time information IGT, termination state information IGS, erase position information IGE, interleaver no-output position information INO and delayed interleave start position signal IDS, as generation information for a next stage, synchronously with the frame top.

[0325] Note that the interleaver 100 will be described in detail in Subsection 2.3.

[0326] The address storage circuit 110 includes a plurality of banks of RAMs (random-access memory) and selection circuits (not shown) to hold, as address data, data replacement position information to which reference is made during interleaving or de-interleaving by the interleaver 100. The address data held in the address storage circuit 110 is read as a reading address data ADA when the address of the address storage circuit 110 is specified as address data IAA by the interleaver 100. Also, address data write to the address storage circuit 110 is effected by the control circuit 60. An address data is written as write data CIWD when the address of the address storage circuit 110 is specified as write data CIAD by the control circuit 60. In this way, an arbitrary interleaving pattern can be written to the address storage circuit 110. Note that the address storage circuit 110 may be provided in the interleaver 100. That is, the element decoder 50 makes an interleaving or de-interleaving by means of both the interleaver 100 and address storage circuit 110.

[0327] The selector 120₁ selects, on the basis of the output data selection control signal CITM, any one of the soft-output SOL and extrinsic information SOE supplied from the soft-output decoding circuit 90, and supplies it as data TLX to the selector 120₂. That is, the selector 120₁ is provided to judge whether the soft-output decoding circuit 90 should output extrinsic information in the process of repetitive decoding or a soft-output as a final result.

[0328] The selector 120₂ selects, on the basis of the operation mode information CBF, any one of the delayed extrinsic information SDEX supplied from the soft-output decoding circuit 90 and the data TLX supplied from the selector 120₁, and supplies it as data TDLX to the selectors 120₄ and 120₇.

[0329] The operation modes of the element decoder 50 will be described herebelow. The element decoder 50 is designed to operate in six modes for example. In the first mode of operation of the element decoder 50, the soft-output decoding circuit 90 and interleaver 100 makes a normal soft-output decoding and interleaving, respectively. In the second mode, only the soft-output deciding circuit 90 makes the normal soft-output decoding. In the third mode, only the interleaves 100 makes the normal interleaving. In the fourth mode, the soft-output decoder 90 and interleaver 100 function as delay circuits, respectively, without making any normal soft-output decoding and interleaving. In the fifth mode, only the soft-output decoder 90 functions as a delay circuit without making any normal soft-output decoding. In the sixth mode, only the interleaver 100 functions as a delay circuit without making any normal interleaving. Any of these operation modes is selected by the control circuit 60, and supplied as the operation mode information CBF to each of the soft-output decoder 90 and interleaver 100. In the following, the first to third modes of operation will be referred to as “normal mode”, while the fourth to sixth modes will be referred to as “delay mode”, as necessary.

[0330] More specifically, when the operation mode information CBF indicates a delay mode for a delay for the same time as a time taken for operation by the soft-output decoding circuit 90, by the interleaver 100 or by the soft-output decoding circuit 90 and interleaves 100, the selector 120₂ selects and outputs delayed extrinsic information SDEX. On the other hand, when the operation mode information CBF indicates a normal mode in which the soft-output decoding circuit 90 and/or interleaver 100 should operate without any delay due to the time of operation of the soft-output decoding circuit 90 and/or interleaver 100, the selector 120₂ selects and outputs data TLX. That is, the selector 120₂ is provided to judge whether the operation mode of the element decoder 50 is the delay or normal one. It selects output date correspondingly to each selected one of the modes of operation.

[0331] The selector 120₃ selects, on the basis of the operation mode information CBF, any one of the received value TR and delayed received value SDR supplied from the soft-output decoding circuit 90, and supplies it as data TDI to the interleaver 100. More particularly, when the operation mode information CBF indicates the normal mode in which only the interleaver 100 operates or the delay mode for a delay for the same time taken by the interleaver 100 for its operation, the selector 120₃ selects and outputs the received value TR. On the other hand, when the operation mode information CBF indicates any normal or delay mode other than the above, the selector 120₃ selects and outputs the delayed received value SDR. Namely, the selector 120₃ is provided to judge whether input data to the interleaver 100 is a one subjected to the soft-output decoding by the soft-output decoding circuit 90 or delayed the same time as taken by the soft-output decoding circuit 90 for its soft-output decoding operation. It selects output data correspondingly to each selected one of the modes of operation.

[0332] The selector 120₄ selects, based on the operation mode information CBF, any one of the extrinsic information or interleaved data TEXT and the data TDLX supplied from the selector 120₂, and supplies it as data TII to the interleaver 100. More particularly, when the operation mode information CBF is a one indicating a normal mode in which only the interleaver 100 operates or a delay mode for a delay for the same time as taken by the interleaver 100 for its interleaving operation, the selector 120₄ selects and outputs the extrinsic information or interleaved data TEXT. On the other hand, when the operation mode information CBF indicates any normal or delay mode other than the above, the selector 120₄ selects and outputs data TDLX. That is, the selector 120₄ is provided to judge whether input data to the interleaver 100 is a one subjected to the soft-output decoding by the soft-output decoding circuit 90 or delayed the same time as taken by the soft-output decoding circuit 90 for its soft-output decoding operation. It selects output data correspondingly to each selected one of the modes of operation.

[0333] The selector 120₅ selects, based on the operation mode information CBF, either the edge signal TEILS supplied from the edge detection circuit 80 or delayed edge signal SDILS supplied from the soft-output decoding circuit 90, and supplies it as interleave start position signal TIS to the interleaver 100. More specifically, when the operation mode information CBF indicates a normal mode in which only the interleaver 100 operates or a delay mode for a delay for the same time taken by the soft-output decoding circuit 90 for its interleaving operation, the selector 120₅ selects and outputs the edge signal TEILS. On the other hand, when the operation mode information CBF indicates any normal or delay mode other than the above, the selector 120₅ selects and outputs the delay edge signal SDILS. Namely, the selector 120₅ is provided to judge whether input data to the interleaver 100 is a one subjected to the soft-output decoding by the soft-output decoding circuit 90 or delayed the same time taken for the soft-output decoding by the soft-output decoding circuit 90. It selects output data correspondingly to each selected one of the modes of operation.

[0334] The selector 120₆ selects, on the basis of the operation mode information CBF, any one of the delayed received value SDR supplied from the soft-output decoding circuit 90 and interleaving length delayed received value IDO supplied from the interleaver 100, and supplies it as delayed received value TDR to the selector 120₈. More particularly, when the operation mode information CBF indicates a normal mode in which only the soft-output decoding circuit 90 operates or a delay mode for a delay for the same time taken by the soft-output decoding circuit 90 for its operation, the selector 120₆ selects and outputs the delayed received value SDR. On the other hand, when the operation mode information CBF indicates any normal or delay mode other than the above, the selector 120₆ selects and outputs the interleaving length delayed received value IDO. That is, the selector 120₆ is provided to judge whether output data is a one subjected to the interleaving by the interleaver 100 or delayed the same time as taken by the interleaves 100 for its interleaving operation. It selects output data correspondingly to each selected one of the operation modes.

[0335] The selector 120₇ selects, on the basis of the operation mode information CBF, any one of the interleaver output data IIO supplied from the interleaver 100 and data TDLX supplied from the selector 120₂, and supplies it as soft-output TSO to the selector 120₉. More particularly, when the operation mode information CBF indicates a normal mode in which only the soft-output decoding circuit 90 operates or a delay mode for a delay for the same time as taken ration by the soft-output decoding circuit 90 for its operation, the selector 120₇ selects and outputs the data TDLX. On the other hand, when the operation mode information CBF indicates any normal or delay mode other than the above, the selector 120₇ selects and outputs the interleaver output data 110. That is, the selector 120₇ is provided to judge whether output data is a one subjected to the interleaving by the interleaver 100 or delayed the same time as taken by the interleaves 100 for its interleaving operation. It selects output data correspondingly to each selected one of the operation modes.

[0336] The selector 120₈ selects, on the basis of the check mode information CTHR, any one of the delayed received value TDR supplied from the selector 120₆ and through signal transmitted over the signal line 130, and outputs it as delayed received value TRN to outside. Note that the delayed received value TRN is outputted as delayed received value RN. That is, the selector 120₈ is provided to judge whether delayed received value to a next element decoder should be outputted or system check should be done.

[0337] The selector 120₉ selects, on the basis of the check mode information CTHR, any one of the soft-output TSO supplied from the selector 120₇ and through signal transmitted over the signal line 130, and outputs it as soft-output TINT to outside. Note that the soft-output TINT is outputted as soft-output INT. That is, the selector 120₉ is provided to judge whether soft-output to a next element decoder should be outputted or system check should be done.

[0338] The selector 120₁₀ selects, on the basis of the check mode information CTHR, either next generation stage information including the termination time information IGT and termination state information IGS supplied from the interleaver 100, erasure position information IGE and interleaver no-output position information INO, and delayed interleave start position information IDS supplied from the interleaver 100, or the through signal transmitted over the signal line 130, and outputs it as next termination time information TTNPN, next termination state information TTNSN, next erasure time information TERSN and next a priori probability information erasure information TEAPN, and next interleave start position signal TILSN to outside. Note that the next termination time information TTNPN, next termination state information TTNSN, next erasure time information TERSN and next a priori probability information erasure information TEAPN, and next interleave start position signal TILSN are outputted as next termination time information TNPN, next termination state information TNSN, next erasure position information ERSN and next a priori probability information erasure information EAPN, and next interleave start position signal ILSN, respectively. Namely, the selector 120₁₀ is provided to judge whether next-stage information to the next element decoder should be outputted or system check should be done.

[0339] As will be described in detail later, the signal line 130 is used primarily for making system check in case a decoder 3 similar to the aforementioned decoders 3′ and 3″ is formed by concatenating a plurality of element decoders 50. The signal line 130 is formed by tying together signal lines for transmission of the received value TR, extrinsic information or interleaved data TEXT, erasure information TERS, a priori probability information erasure information TEAP, termination time information TTNP, termination state information TTNS and interleave start position signal TILS, respectively, to supply these signals to the selectors 120₈, 120₉ and 120₁₀.

[0340] The element decoder 50 is equivalent to a module including at least a soft-output decoding circuit and interleaver or de-interleaver as shown by a dash-line block in FIG. 7 or 9 for example. A plurality of such element decoders 50 is concatenated to each other to form the decoder 3 capable of decoding an arbitrary one of the PCCC, SCCC, TTCM and SCTCM codes. Note that various features of the element decoder 50 will further be described in Section 4.

[0341] The soft-output decoding circuit 90 and interleaver 100 will be described in detail herebelow.

[0342] 2.2 Detailed Description of the Soft-Output Decoding Circuit

[0343] First, the description will start with the soft-output decoding circuit 90. As schematically illustrated in FIG. 15, the soft-output decoder 90 includes a code information generation circuit 151 to generate code information on the element encoders in the encoder 1, an inner erasure information generation circuit 152 to generate inner erasure information indicative a puncture pattern in the encoder 1, a termination information generation circuit 153 to generate termination information in the encoder 1, a received value and a priori probability information selection circuit 154 to select received data and a priori probability information to be entered for decoding and substitute a symbol whose likelihood is “0” for a position where no coded output exists, a received data and delaying-use data storage circuit 155 to store both a received data and delayed data, an Iγ computation circuit 156 to compute a log likelihood Iγ being a first log likelihood, an Iγ distribution circuit 157 to distribute the log likelihood Iγ computed correspondingly to the encoder 1, an Iα computation circuit 158 to compute a log likelihood Iβ being a second log likelihood, an Iβ computation circuit 159 to compute a log likelihood Iβ being a third log likelihood, an Iβ storage circuit 160 to store the computed a log likelihood Iβ, a soft-output computation circuit 161 to compute a log soft-output Iλ, a received value or a priori probability information separation circuit 162 to separate a received value and a priori probability information from each other, an extrinsic information computation circuit 163, an amplitude adjusting/clipping circuit 164 to adjust the amplitude of the log soft-output Iλ and clip it to a predetermined dynamic range, and a hard decision circuit 165 to make a hard decision of a soft-output and received value to be decoded.

[0344] The left half of the soft-output decoding circuit 90 shown in FIG. 15 is shown in detail in FIG. 16, while the right half is shown in detail in FIG. 17.

[0345] The code information generation circuit 151 generates, based on the rate information CRAT and generator matrix information CG supplied from the control circuit 60, code information on the element encoder in the encoder 1. More particularly, the code information generation circuit 151 generates number-of-input-bits information IN indicating the number of input bits to the element encoder in the encoder 1, type information WM indicating of which type of the convolutional encoder is, Wozencraft or Massey, when the element encoder in the encoder 1 is the convolutional encoder, number-of-memories information MN indicating the number of shift registers in the element encoder in the encoder 1, that is, memories representing a state (transition state), branch input/output information BIO indicating input/output information extending along the time base of each of the branches in a trellis being a diagram of the state transition of the element encoder in the encoder 1, and valid output position information PE indicating the output position validity showing that there exists an output from the element encoder in the encoder 1 and there exists a received value corresponding to the output.

[0346] The convolutional encoders of the Wozencraft and Massey's will be described herebelow.

[0347] First, the Wozencraft's convolutional encoder consists of delay elements and a combinatorial circuit to hold data in time sequence in relation to the delay elements. An example of the Wozencraft's convolutional encoder is shown in FIG. 18 for example. As shown, the Wozencraft's convolutional encoder includes four shift registers 201₁, 201₂, 201₃ and 201₄, and a combinatorial circuit including sixteen exclusive OR circuits 202₁, 202₂, 202₃, 202₄, 202₅, 202₆, 202₇, 202₈, 202₉, 202₁₀, 202₁₁, 202₁₂, 202₁₃, 202₁₄, 202₁₅ and 202₁₆ and twenty AND gates G0[0], GB[0], GB[1], GB[2], GB[3], G1[]0, G1[1], G1[2], G1[3], G1[4], G2[0], G2[1], G2[2], G2[3], G2[4], G3[0], G3[1], G3[2], G3[3] and G3[4]. This example of Wozencraft's convolutional encoder makes a convolutional operation of “¼” in rate. Note that in this convolutional encoder, the AND gates G0[0], GB[0], GB[1], GB[2], GB[3], G1[0], G1[1], G1[2], G1[3], G1[4], G2[0], G2[1], G2[2], G2[3], G2[4], G3[0], G3[1], G3[2], G3[3] and G3[4] are used as selectively connected to each other according to the configuration of a code, and all of them are not used. That is, in the convolutional encoder, the combinatorial circuit varies depending upon these AND gates G0[0], GB[0], GB[1], GB[2], GB[3], G1[0], G1[1], G1[2], G1[3], G1[4], G2[0], G2[1], G2[2], G2[3], G2[4], G3[0], G3[1], G3[2], G3[3] and G3[4], and the configuration of the code varies correspondingly. Thus, the convolutional encoder can make a Wozencraft's convolution with a maximum number of states being “2⁴=16”. The generator matrix G of the convolutional encoder is given by the following expression (27). The terms GB(D), G1(D), G2(D) and G3(D) in the expression (27) are given by the expressions (28) to (31), respectively.

[0348] $\begin{array}{cc}G=\left[\mathrm{G0}\mathrm{G1}\left(D\right)\mathrm{G2}\left(D\right)\frac{\mathrm{G3}\left(D\right)}{\mathrm{GB}\left(D\right)\mathrm{GB}\left(D\right)\mathrm{GB}\left(D\right)}\right]& \left(27\right)\end{array}$
GB(D)=1+GB[0]D+GB[1]D²+GB[2]D³+GB[3]D⁴  (28)
G1(D)=G1[0]+G1[1]D+G1[2]D²+G1[3]D³+G1[4]D⁴  (29)
G2(D)=G2[0]+G2[1]D+G2[2]D²+G2[3]D³+G2[4]D⁴  (30)
G3(D)=G3[0]+G3[1]D+G3[2]D²+G3[3]D³+G3[4]D⁴  (31)

[0349] Another example of the Wozencraft's convolutional encoder is shown in FIG. 19 for example. As shown, it includes three shift registers 203₁, 203₂ and 203₃ and a combinatorial circuit including twelve exclusive OR circuits 204₁, 204₂, 204₃, 204₄, 204₅, 204₆, 204₇, 204₈, 204₉, 204₁₀, 204₁₁, and 204₁₂ and fifteen AND gates G1[0], G1[1], G1[2], G1[3] G1[4], G2[0], G2[1], G2[2], G2[3], G2[4], G3[0], G3[1], G3[2], G3[3] and G3[4]. This example of Wozencraft's convolutional encoder makes a convolutional operation at a rate of “⅔”. Note that also in this convolutional encoder, the AND gates G1[0], G1[1], G1[2], G1[3] G1[4], G2[0], G2[1], G2[2], G2[3], G2[4], G3[0], G3[1], G3[2], G3[3] and G3[4] are use d as selectively connected to each other according to the configuration of a code, and all of them are not used. That is, in the convolutional encoder, the combinatorial circuit varies depending upon these AND gates, and the configuration of the code varies correspondingly. Thus, the convolutional encoder can make a Wozencraft's convolution with a maximum number of states being “2³=8”. The generator matrix G of the convolutional encoder is given by the following expression (32). The terms G11(D), G21(D), G31(D), G12(D), G22(D) and G32(D) in the expression (32) are given by the expressions (33) to (38), respectively.

[0350] $\begin{array}{cc}G=\left[\begin{array}{c}\mathrm{G11}\left(D\right)\mathrm{G21}\left(D\right)\mathrm{G31}\left(D\right)\\ \mathrm{G12}\left(D\right)\mathrm{G22}\left(D\right)\mathrm{G32}\left(D\right)\end{array}\right]& \left(32\right)\end{array}$
G11(d)=G1[0]+G1[1]D+G1[2]D²  (33)
G21(d)=G2[0]+G2[1]D+G2[2]D²  (34)
G31(d)=G3[0]+G3[1]D+G3[2]D²  (35)
G12(d)=G1[3]+G1[4]D  (36)
G22(d)=G2[3]+G2[4]D  (37)
G32(d)=G3[3]+G3[4]D  (38)

[0351] On the other hand, the Massey's convolutional encoder includes delay elements and a combinatorial circuit to output any of input bits as it is as a component and not to hold data in time sequence in relation to the delay elements. An example of the Massey's convolutional encoder is shown in FIG. 20 for example. As shown, it includes three shift registers 205₁, 205₂ and 205₃, four exclusive OR circuits 206₁, 206₂, 206₃ and 206₄, and eleven AND gates GB[0], GB[1], GB[2], G1[0], G1[1], G1[2], G1[3], G2[0], G2[1], G2[2] and G2[3]. This example of Massey's convolutional encoder makes a convolutional operation of “⅔” in rate. Note that also in this convolutional encoder, the AND gates GB[0], GB[1], GB[2], G1[0], G1[1], G1[2], G1[3], G2[0], G2[1], G2[2] and G2[3] are used as selectively connected to each other according to the configuration of a code, and all of them are not used. That is, in the convolutional encoder, the combinatorial circuit varies depending upon these AND gates GB[0], GB[1], GB[2], G1[0], G1[1], G1[2], G1[3], G2[0], G2[1], G2[2] and G2[3], and the configuration of the code varies correspondingly. Thus, the convolutional encoder can make a Massey's convolution with a maximum number of states being “2³=8”. The generator matrix G of the convolutional encoder is given by the following expression (39). The terms GB(D), G1(D) and G2(D) in the expression (39) are given by the expressions (40) to (42), respectively.

[0352] $\begin{array}{cc}G=\left[\begin{array}{ccc}1& 0& \frac{\mathrm{G1}\left(D\right)}{\mathrm{GB}\left(D\right)}\\ 0& 1& \frac{\mathrm{G2}\left(D\right)}{\mathrm{GB}\left(D\right)}\end{array}\right]& \left(39\right)\end{array}$
GB(D)=1+GB[0]D+GB[1]D²+GB[2]D³  (40)
G1(D)=G1[0]+G1[1]D+G1[2]D²+G1[3]D³  (41)
G2(D)=G2[0]+G2[1]D+G2[2]D²+G2[3]D³  (42)

[0353] An example of the Massey's convolutional encoder is shown in FIG. 21 for example. As shown, it includes two shift registers 207₁ and 207₂, three exclusive OR circuits 208₁, 208₂ and 208₃, and eleven AND gates GB[0], GB[1], G1[0], G1[1], G1[2], G2[0], G2[1], G2[2], G3[0], G3[1] and G3[2]. This example of Massey's convolutional encoder makes a convolutional operation of “ 3/3” in rate. Note that also in this convolutional encoder, the AND gates GB[0], GB[1], G1[0], G1[1], G1[2], G2[0], G2[1], G2[2], G3[0], G3[1] and G3[2] are used as selectively connected to each other according to the configuration of a code, and all of them are not used. That is, in the convolutional encoder, the combinatorial circuit varies depending upon these AND gates GB[0], GB[1], G1[0], G1[1], G1[2], G2[0], G2[1], G2[2], G3[0], G3[1] and G3[2], and the configuration of the code varies correspondingly. Thus, the convolutional encoder can make a Massey's convolution with a maximum number of states being “2²=4”. The generator matrix G of the convolutional encoder is given by the following expression (43). The terms GB(D), G1(D), G2(D) and G3(D) in the expression (43) are given by the expressions (44) to (47), respectively.

[0354] $\begin{array}{cc}G=\left[\begin{array}{ccc}1& 0& \frac{\mathrm{G1}\left(D\right)}{\mathrm{GB}\left(D\right)}\\ 0& 1& \frac{\mathrm{G2}\left(D\right)}{\mathrm{GB}\left(D\right)}\\ 0& 0& \frac{\mathrm{G3}\left(D\right)}{\mathrm{GB}\left(D\right)}\end{array}\right]& \left(43\right)\end{array}$
GB(D)=1+GB[0]D+GB[1]D²  (44)
G1(D)=G1[0]+G1[1]D+G1[2]D²  (45)
G2(D)=G2[0]+G2[1]D+G2[2]D²  (46)
G3(D)=G3[0]+G3[1]D+G3[2]D²  (47)

[0355] The information generated by the code information generation circuit 151 will be described in further detail herebelow concerning possible examples of the convolutional encoders of the above types.

[0356] First as the Wozencraft's convolutional encoder shown in FIG. 18, there is provided a one including four shift registers 201₁, 201₂, 201₃ and 201₄ and eleven exclusive OR circuits 202₁, 202₄, 202₅, 202₇, 202₈, 202₁₀, 202₁₂, 202₁₃, 202₁₄, 202₁₅ and 202₁₆ by connecting fifteen AND gates G0[0], GB[2], GB[3], G1[0], G1[1], G1[3], G1[4], G2[0], G2[2], G2[4], G3[0], G3[1], G3[2], G3[3] and G3[4]. Supplied with 1-bit input data i₀, the convolutional encoder makes a convolution of the input data i₀ and outputs the result of convolution as an output data of 4 bits O₁, O₁, O₂ and O₃.

[0357] The trellis of this convolutional encoder is depicted as shown in FIG. 23. As shown, the label on each branch indicates a number for the branch. The relation between states before and after a transition and input data/output data for the branch number is as shown in Table 1. In Table 1, the “states” columns sequentially list the contents of the shift registers 201₄, 201₃, 201₂ and 201₁, representing state numbers “0000”, “0001”, “0010”, “0011”, “0100”, “0101”, “0110”, “0111”, “1000”, “1001”, “1010”, “1011”, “1100”, “1101”, “1110” and “1111” by “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9”, “10”, “11”, “12”, “13”, “14”, “15”, respectively. Also, the “input/output data” are i₀/O₃, O₂, O₁ and O₀.

[0358]

TABLE 1
Various Kinds of Information for Branch Numbers
Branch No.	Preceding state	Input data/output data	Next state
0	0	0/0000	0
1	0	1/1111	1
2	1	0/1010	2
3	1	1/0101	3
4	2	0/1100	4
5	2	1/0011	5
6	3	0/0110	6
7	3	1/1001	7
8	4	1/1011	8
9	4	0/0100	9
10	5	1/0001	10
11	5	0/1110	11
12	6	1/0111	12
13	6	0/1000	13
14	7	1/1101	14
15	7	0/0010	15
16	8	1/1111	0
17	8	0/0000	1
18	9	1/0101	2
19	9	0/1010	3
20	10	1/0011	4
21	10	0/1100	5
22	11	1/1001	6
23	11	0/0110	7
24	12	0/0100	8
25	12	1/1011	9
26	13	0/1110	10
27	13	1/0001	11
28	14	0/1000	12
29	14	1/0111	13
30	15	0/0010	14
31	15	1/1101	15

[0359] Thus, the states of the convolutional encoder shown in FIG. 22 count 16 in number. The trellis is structured such that two paths run from each state to states at a next time, and thus it has a total of 32 branches.

[0360] In this convolutional encoder, the code information generation circuit 151 generates “1 bit” for the number-of-input-bits information IN, “Wozencraft's” for the type information WM, “4” for the number-of-memories information MN, and an input/output pattern of each branch as shown in Table 1 for the branch input/output information BIO.

[0361] Also, as the Wozencraft's convolutional encoder shown in FIG. 19, there is provided a one including three shift registers 203₁, 203₂ and 203₃ and six exclusive OR circuits 204₅, 204₆, 204₉, 204₁₀, 204₁₁ and 204₁₂ by connecting nine AND gates G1[2], G1[3], G2[2], G2[4], G3[0], G3[1], G3[2], G3[3] and G3[4]. Supplied with 2bit input data i₀ and i₁ the convolutional encoder makes convolution of the input data i₀ and i₁ outputs the result of convolution as a 3-bit output data O₀, O₁ and O₂.

[0362] The trellis of this convolutional encoder is depicted as shown in FIG. 25. As shown, the label on each branch indicates a number for the branch. The relation between states before and after a transition and input data/output data for the branch number is as shown in Table 2. In Table 2, the “states” columns sequentially list the contents of the shift registers 203₃, 203₂ and 203₁, representing state numbers “000”, “001”, “010”, “011”, “100”, “101”, “110” and “111” by “0”, “1”, “2”, “3”, “4”, “5”, “6” and “7”, respectively. Also, the “input/output data” are i₁, i₀/O₂, O₁ and O₀.

[0363]

TABLE 2
Various Kinds of Information for Branch Numbers
Branch No.	Preceding state	Input data/output data	Next state
0	0	00/000	0
1	0	01/110	1
2	0	10/101	2
3	0	11/011	3
4	1	00/100	4
5	1	01/010	5
6	1	10/001	6
7	1	11/111	7
8	2	00/110	0
9	2	01/000	1
10	2	10/011	2
11	2	11/101	3
12	3	00/010	4
13	3	01/100	5
14	3	10/111	6
15	3	11/001	7
16	4	00/101	0
17	4	01/011	1
18	4	10/000	2
19	4	11/110	3
20	5	00/001	4
21	5	01/111	5
22	5	10/100	6
23	5	11/010	7
24	6	00/011	0
25	6	01/101	1
26	6	10/110	2
27	6	11/000	3
28	7	00/111	4
29	7	01/001	5
30	7	10/010	6
31	7	11/100	7

[0364] Thus, the states of the convolutional encoder shown in FIG. 24 count 8 in number. The trellis is structured such that four paths run from each state to states at a next time, and thus it has a total of 32 branches.

[0365] In this convolutional encoder, the code information generation circuit 151 generates “2 bits” for the number-of-input-bits information IN, “Wozencraft's” for the type information WM, “3” for the number-of-memories information MN, and an input/output pattern of each branch as shown in Table 2 for the branch input/output information BIO.

[0366] Also, as the Wozencraft's convolutional encoder shown in FIG. 20, there is available a one including three shift registers 205₁, 205₂, 205₃ and two exclusive-OR circuits 206₂ and 206₃ as shown in FIG. 26 by connecting three AND gates GB[2], G1[2], G2[1]. Supplied with 2-bit input data i₀ and i₁, the convolutional encoder makes a convolution of the input data i₀ and i₁ and outputs the result of convolution as a 3-bit output data O₀, O₁ and O₂.

[0367] The trellis of this convolutional encoder is depicted as shown in FIG. 27. As shown, the label on each branch indicates a number for the branch. The relation between states before and after a transition and input data/output data for the branch number is as shown in Table 3. In Table 3, the “states” columns sequentially list the contents of the shift registers 205₁, 205₂ and 205₃, representing state numbers “000”, “001”, “010”, “011”, “100”, “101”, “110” and “111” by “0”, “1”, “2”, “3”, “4”, “5”, “6” and “7”, respectively. Also, the “input/output data” are i₁, i₀/O₂, O₁ and O₀.

[0368]

TABLE 3
Various Kinds of Information for Branch Numbers
Branch No.	Preceding state	Input data/output data	Next state
0	0	00/000	0
1	0	10/010	1
2	0	01/001	2
3	0	11/011	3
4	1	00/100	4
5	1	10/110	5
6	1	01/101	6
7	1	11/111	7
8	2	10/010	0
9	2	00/000	1
10	2	11/011	2
11	2	01/001	3
12	3	10/110	4
13	3	00/100	5
14	3	11/111	6
15	3	01/101	7
16	4	01/001	0
17	4	11/011	1
18	4	00/000	2
19	4	10/010	3
20	5	01/101	4
21	5	11/111	5
22	5	00/100	6
23	5	10/110	7
24	6	11/011	0
25	6	01/001	1
26	6	10/010	2
27	6	00/000	3
28	7	11/111	4
29	7	01/101	5
30	7	10/110	6
31	7	00/100	7

[0369] Thus, the states of the convolutional encoder shown in FIG. 26 count 8 in number. The trellis is structured such that four paths run from each state to states at a next time, and thus it has a total of 32 branches.

[0370] In this convolutional encoder, the code information generation circuit 151 generates “2 bits” for the number-of-input-bits information IN, “Massey” for the type information WM, “3” for the number-of-memories information MN, and an input/output pattern of each branch as shown in Table 3 for the branch input/output information BIO.

[0371] Also, as the Massey's convolutional encoder shown in FIG. 21, there is provided a one including two shift registers 207₁ and 207₂, and three exclusive OR circuits 208₁, 208₂ and 208₃ by connecting six AND gates GB[1], G1[0], G1[1], G1[2], G2[0], and G3[0]. Supplied with 3-bit input data i₀, i₁ and i₂ the convolutional encoder makes a convolution of the input data i₀, i₁ and i₂ and outputs the result of convolution as a 3-bit output data O₀, O₁ and O₂.

[0372] The trellis of this convolutional encoder is depicted as shown in FIG. 29. As shown, the label on each branch indicates a number for the branch. The relation between states before and after a transition and input data/output data for the branch number is as shown in Table 4. In Table 4, the “states” columns sequentially list the contents of the shift registers 207₁ and 207₂, representing state numbers “00”, “01”, “10” and “11” by “0”, “1”, “2” and “3”, respectively. Also, the “input/output data” are i₂, i₁, i₀/O₂, O₁ and O₀.

[0373]

TABLE 4
Various Kinds of Information for Branch Numbers
Branch No.	Preceding state	Input data/output data	Next state
0	0	000/000	0
1	0	110/010	0
1	0	001/101	1
3	0	111/111	1
4	0	010/110	2
5	0	100/100	2
6	0	101/001	3
7	0	011/011	3
8	1	010/010	0
9	1	100/000	0
10	1	101/101	1
11	1	011/111	1
12	1	110/110	2
13	1	000/100	2
14	1	001/001	3
15	1	111/011	3
16	2	001/101	0
17	2	111/111	0
18	2	000/000	1
19	2	110/010	1
20	2	101/001	2
21	2	011/011	2
22	2	010/110	3
23	2	100/100	3
24	3	101/101	0
25	3	011/111	0
26	3	010/010	1
27	3	100/000	1
28	3	111/011	2
29	3	001/001	2
30	3	000/100	3
31	3	110/110	3

[0374] Thus, the states of the convolutional encoder shown in FIG. 28 count 4 in number. The trellis is structured such that four sets of parallel paths run from each state to states at a next time, and thus it has a total of 32 branches.

[0375] In this convolutional encoder, the code information generation circuit 151 generates “3 bits” for the number-of-input-bits information IN, “Massey” for the type information WM, “2” for the number-of-memories information MN, and an input/output pattern of each branch as shown in Table 4 for the branch input/output information BIO.

[0376] As above, the code information generation circuit 151 generates code information corresponding to the element encoder in the encoder 1. Especially, the code information generation circuit 151 computes input/output patterns for all the branches of the trellis, corresponding to a code to be decoded, to generate branch input/output information BIO which will be described in detail later. The code information generation circuit 151 supplies the generated number-of-input-bits information IN to the termination information generation circuit 153, received value and a priori probability information selection circuit 154, Iγ computation circuit 156, Iγ distribution circuit 157, Iα computation circuit 158, Iβ computation circuit 159, soft-output computation circuit 161, received value or a priori probability information separation circuit 162 and hard decision circuit 165. Further, the code information generation circuit 151 supplies the generated type information WM to the Iγ computation circuit 156, Iγ distribution circuit 157, Iα computation circuit 158 and Iβ computation circuit 159. Also, the code information generation circuit 151 supplies the generated number-of-memories information MN to the termination information generation circuit 153, Iγ distribution circuit 157, Iα computation circuit 158, Iβ computation circuit 159 and soft-output computation circuit 161. Furthermore, the code information generation circuit 151 supplies the thus generated branch input/output information BIO to the Iγ distribution circuit 157 and soft-output computation circuit 161. Also, the code information generation circuit 151 supplies the generated valid output position information PE to the inner erasure information generation circuit 152.

[0377] The inner erasure information generation circuit 152 is supplied with erasure information TERS from outside and valid output position information PE from the code information generation circuit 151 to generate, based on the supplied information, inner erasure position information IERS indicating a position where there does not exist any coded output which will be obtained via general consideration of the puncture pattern and valid output position.

[0378] More specifically, the inner erasure information generation circuit 152 can be implemented as a one including four OR gates 211₁, 211₂, 211₃ and 211₄ as shown in FIG. 30 for example.

[0379] Each of the OR gates 211₁, 211₂, 211₃ and 211₄ carries output the logical OR between the erasure information TERS and data obtained by inverting the valid output position information PE supplied from the code information generation circuit 151. Each of the OR gates 211₁, 211₂, 211₃ and 211₄ supplies the thus obtained logical sum or OR as inner erasure position information IERS to the received value and a priori probability information selection circuit 154.

[0380] By making the OR operation by the OR gates 211₁, 211₂, 211₃ and 211₄ as above, the inner erasure information generation circuit 152 generates the inner erasure position information IERS indicating a position where no coded output exists.

[0381] The termination information generation circuit 153 is supplied with termination time information TTNP and termination state information TTNS from outside and number-of-input bits information IN and number-of-memories information MN from the code information generation circuit 151 to generate termination information in the encoder 1 based on these pieces of information. More particularly, the termination information generation circuit 153 generates, based on the termination time information TTNP, termination state information TTNS, number-of-input-bits information IN and number-of-memories information MN, termination time information TPM indicating a termination time, and termination state information TSM indicating a termination state, in the encoder 1.

[0382] As shown in FIG. 31 for example, the termination information generation circuit 153 can be implemented as a one including a plurality of registers 212₁, 212₂, 212₃, 212₄, 212₅ and 212₆, a plurality of selectors 213₁, 213₂, 213₃, 213₄, 213₅, 213₆, 213₇, 213₈ and 213₉, and an AND gate 214.

[0383] The register 212₁ holds, for one clock, the termination time information TTNP supplied from outside, and supplies the thus held termination tine information TTNP to the registers 212₂ and selector 213₃.

[0384] The register 212₂ holds, for one clock, the termination time information TTNP supplied from the register 212₁, and supplies the thus held termination time information TTNP to the register 212₃ and selector 213₄.

[0385] The register 212₃ holds, for one clock, the termination time information TTNP supplied from the register 212₂, and supplies the thus held termination time information TTNP to the selector 213₅.

[0386] The register 212₄ holds, for one clock, the termination state information TTNS supplied from outside, and supplies the thus held termination state information TTNS to the register 212₅ and selector 213₆.

[0387] The register 212₅ holds, for one clock, the termination state information TTNS supplied from the register 212₄, and supplies the thus held termination state information TTNS to the register 212₆ and selector 213₇.

[0388] The register 212₆ holds, for one clock, the termination state information TTNS supplied from the register 212₅, and supplies the thus held termination state information TTNS to the selector 213₈.

[0389] The selector 213₁ selects, based on the number-of-input-bits information IN, either information that the number of memories in the element encoder in the encoder 1 is “1” or information that the number of memories is “2”, of the number-of-memories information MN. Specifically, when the number of input bits to the encoder 1 is “1” for example, the selector 213₁ selects the information that the number of memories is “1”. The selector 213₁ supplies the thus selected data as a selection control signal to the selector 213₃.

[0390] The selector 213₂ selects, based on the number-of-input-bits information IN, either information that the number of memories in the element encoder in the encoder 1 is “2” or information that the number of memories is “3”, of the number-of-memories information MN. Specifically, when the number of input bits to the encoder 1 is “1” for example, the selector 213₂ selects the information that the number of memories is “2”. The selector 213₂ supplies the thus selected data as a selection control signal to the selector 213₄.

[0391] The selector 213₃ selects, based on the data selected by the selector 213₁, either the termination time information TTNP supplied from the register 212₁ or data whose value is “1”. Specifically, when the number of memories in the element encoder in the encoder 1 is “1”, the selector 213₃ selects the termination time information TTNP supplied from the register 212₁. The selector 213₃ supplies the thus selected data to the AND gate 214.

[0392] The selector 213₄ selects, based on the data selected by the selector 213₂, either the termination time information TTNP supplied from the register 212₂ or data whose value is “1”. Specifically, when the number of memories in the element encoder in the encoder 1 is “2”, the selector 213₄ selects the termination time information TTNP supplied from the register 212₂. The selector 213₄ supplies the thus selected data to the AND gate 214.

[0393] The selector 213₅ selects, based on the number-of-memories information MN, either the termination time information TTNP supplied from the register 212₃ or data whose value is “1”. Specifically, when the number of memories in the element encoder in the encoder 1 is “3”, the selector 213₅ selects the termination time information TTNP supplied from the register 212₃. The selector 213₅ supplies the thus selected data to the AND gate 214.

[0394] The selector 213₆ selects, based on the number-of-memories information MN, either the termination state information TTNS supplied from the register 212₄ or data whose value is “0”. Specifically, when the number of memories in the element encoder in the encoder 1 is “1”, the selector 213₆ selects the termination state information TTNS supplied from the register 212₄. The selector 213₆ supplies the thus selected data to the selector 213₈.

[0395] The selector 213₇ selects, based on the number-of-memories information MN, either the termination state information TTNS supplied from the register 212₅ or data whose value is “0”. Specifically, when the number of memories in the element encoder in the encoder 1 is “2”, the selector 213₇ selects the termination state information TTNS supplied from the register 212₅. The selector 213₇ supplies the thus selected data to the selector 213₈.

[0396] The selector 213₈ selects, based on the number-of-memories information MN, either the termination state information TTNS supplied from the register 212₆ or data whose value is “0”. Specifically, when the number of memories in the element encoder in the encoder 1 is “3”, the selector 213₈ selects the termination state information TTNS supplied from the register 212₆. The selector 213₈ supplies the thus selected data to the selector 213₉.

[0397] The selector 213₉ selects, based on the number-of-input-bits information IN, either the termination state information TTNS supplied from outside or data supplied from the selectors 213₆, 213₇ and 213₈. The selector 213₉ supplies the thus selected data as termination state information TSM to the received data and delaying-use data storage circuit 155.

[0398] The AND gate 214 carries out the logical AND between the termination time information TTNP supplied from outside and data supplied from the selectors 213₃, 213₄ and 213₅. The AND gate 214 supplies the thus obtained logical product or AND as termination time information TPM to the received data and delaying-use data storage circuit 155.

[0399] The termination information generation circuit 153 can detect a termination period based on the number-of-memories information MN, and generate termination information for an arbitrary termination period by selecting data corresponding to the detected termination period by means of the selectors 215₃, 215₄, 215₅, 215₆, 215₇ and 215₈. Especially, as will be described in detail later, when the element encoder in the encoder 1 is a Wozencraft's convolutional encoder, the termination information generation circuit 153 generates, as termination information, number-of-input-bits information for the termination period to specify a termination state. On the other hand, when the element encoder in the encoder 1 is any convolutional encoder other than the Wozencraft's one, such as a Massey's convolutional encoder, the termination information generation circuit 153 generates, as termination information, information indicating a termination state in one time slot to specify the termination state for the one time slot.

[0400] The received value and a priori probability information selection circuit 154 is provided to decode an arbitrary code as will be described in detail later. This circuit 154 selects a to-be-decoded input received value TSR and extrinsic information or interleaved data TEXT, whichever is necessary for soft-output decoding, based on the received value type information CRTY supplied from the control circuit 60, number-of-input-bits information IN supplied from the code information generation circuit 151, a priori probability information erasure information TEAP supplied from outside, and the inner erasure position information IERS supplied from the inner erasure information generation circuit 152. Also, as will further be described later, the received value and a priori probability information selection circuit 154 substitutes, based on the inner erasure position information IERS supplied from the inner erasure information generation circuit 152, a symbol whose likelihood is “0” for a position where there exists no coded output. That is, the received value and a priori probability information selection circuit 154 outputs such information as assures a probability in which a bit corresponding to a position where there is no coded output is “0” or “1” to be “½”.

[0401] More specifically, on the assumption that the to-be-decoded received value TSR consists of four sequences of to-be-decoded received values TSR0, TSR1, TSR2 and TSR3 and the extrinsic information or interleaved data TEXT consists of three sequences of extrinsic information or interleaved data TEXT0, TEXT1 and TEXT2, for example, the received value and a priori probability information selection circuit 154 can be implemented as a one including sixteen selectors 215₁, 215₂, 215₃, 215₄, 215₅, 215₆, 215₇, 215₈, 215₉, 215₁₀, 215₁₁, 215₁₂, 215₁₃, 215₁₄, 215₁₅, and 215₁₆ as shown in FIG. 32 for example.

[0402] The selector 215₁ selects, based on the received value type information CRTY, either the to-be-decoded received value TSR0 or extrinsic information or interleaved data TEXT0. More particularly, when the received value type information CRTY indicates extrinsic information, the selector 215₁ selects the extrinsic information or interleaved data TEXT0. The selector 215₁ supplies the thus selected data to the selector 215₈.

[0403] The selector 215₂ selects, based on the received value type information CRTY, either the to-be-decoded received value TSR1 or extrinsic information or interleaved data TEXT1. More particularly, when the received value type information CRTY indicates extrinsic information, the selector 215₂ selects the extrinsic information or interleaved data TEXT1. The selector 215₂ supplies the thus selected data to the selector 215₉.

[0404] The selector 215₃ selects, based on the received value type information CRTY, either the to-be-decoded received value TSR2 or extrinsic information or interleaved data TEXT2. More particularly, when the received value type information CRTY indicates extrinsic information, the selector 215₃ selects the extrinsic information or interleaved data TEXT2. The selector 215₃ supplies the thus selected data to the selector 215₁₀.

[0405] The selector 215₄ selects, based on the received value type information CRTY, either extrinsic information or interleaved data TEXT0 or a priori probability information whose value is “0”. More particularly, when the received value type information CRTY indicates extrinsic information, the selector 215₄ selects the a priori probability information whose value is “0”. The selector 215₄ supplies the thus selected data to the selector 215₁₂.

[0406] The selector 215₅ selects, based on the received value type information CRTY, either extrinsic information or interleaved data TEXT1 or a priori probability information whose value is “0”. More particularly, when the received value type information CRTY indicates extrinsic information, the selector 215₅ selects the a priori probability information whose value is “0”. The selector 215₅ supplies the thus selected data to the selector 215₁₃.

[0407] The selector 215₆ selects, based on the received value type information CRTY, either extrinsic information or interleaved data TEXT2 or a priori probability information whose value is “0”. More particularly, when the received value type information CRTY indicates extrinsic information, the selector 215₆ selects the a priori probability information whose value is “0”. The selector 215₆ supplies the thus selected data to the selector 215₁₄.

[0408] Based on the received value type information CRTY, the selector 215₇ selects, of the inner erasure position information IERS, either information that the first symbol does not exist in output bits from the element encoder in the encoder 1 or information that the second symbol does not. More particularly, when the received value type information CRTY indicates that the encoder 1 is not to code data with TTCM or SCTCM, the selector 215₇ selects the information that the second symbol does not exist, and supplies the selected data as selection control signal to the selector 215₉. Note that the selecting operation of the selector 215₇ is caused by the erasing operation made when the encoder 1 is to code TTCM or SCTCM code. That is, since the erasing operation to be done when the encoder 1 is to code data with TTCM or SCTCM leads to erasure of both symbols of common-phase and orthogonal components, the selector 215₇ will select the information indicating that the second symbol does not exist.

[0409] The selector 215₈ selects either the data supplied from the selector 215₁ or information whose value is “0” based on the inner erasure position information IERS. More specifically, when the inner erasure position information IERS indicates that of the output bits from the element encoder of the encoder 1, the first symbol does not exist, the selector 215₈ selects the information whose value is “0”. The data selected by this selector 215₈ is tied together with the data supplied from the selectors 215₉, 215₁₀, 215₁₄, 215₁₅ and 215₁₆, and supplied as selected received value and a priori probability information RAP to the received data and delaying-use data storage circuit 155.

[0410] The selector 215₉ selects, based on the data supplied from the selector 215₇, either the data supplied from the selector 215₂ or information whose value is “0”. More specifically, when the data supplied from the selector 215₇ indicates that of the output bits from the element encoder of the encoder 1, the second symbol does not exist, the selector 215₉ selects the information whose value is “0”. The data selected by this selector 215₉ is tied together with the data supplied from the selectors 215₈, 215₁₀, 215₁₄, 215₁₅ and 215₁₆, and supplied as selected received value and a priori probability information RAP to the received data and delaying-use data storage circuit 155.

[0411] Based on the inner erasure position information IERS, the selector 215₁₀ selects either the data supplied from the selector 215₃ or information whose value is “0”. More specifically, when the inner erasure position information IERS indicates that of the output bits from the element encoder of the encoder 1, the third symbol does not exist, the selector 215₁₀ selects the information whose value is “0”. The data selected by this selector 215₁₀ is tied together with the data supplied from the selectors 215₈, 215₉, 215₁₄, 215₁₅ and 215₁₆, and supplied as selected received value and a priori probability information RAP to the received data and delaying-use data storage circuit 155.

[0412] The selector 215₁₁ selects, based on the inner erasure position information IERS, either the to-be-decoded received value TSR3 or information whose value is “0”. More specifically, when the inner erasure position information IERS indicates that of the output bits from the element encoder of the encoder 1, the fourth symbol does not exist, the selector 215₁₁ selects the information whose value is “0”. The data selected by this selector 215₁₁ is supplied to the selector 215₁₅.

[0413] The selector 215₁₂ selects, based on the a priori probability information erasure information TEAP, either the data supplied from the selector 215₄ or information whose value is “0”. More specifically, when the a priori probability information erasure information TEAP indicates that the data has been punctured, the selector 215₁₂ selects the information whose value is “0” and supplies it to the selectors 215₁₅ and 215₁₆.

[0414] The selector 215₁₃ selects, based on the a priori probability information erasure information TEAP, either the data supplied from the selector 215₅ or information whose value is “0”. More specifically, when the a priori probability information erasure information TEAP indicates that the data has been punctured, the selector 215₁₃ selects the information whose value is “0”, and supplies the thus selected information to the selector 215₁₆.

[0415] The selector 215₁₄ selects, based on the a priori probability information erasure information TEAP, either the data supplied from the selector 215₆ or information whose value is “0”. More specifically, when the a priori probability information erasure information TEAP indicates that the data has been punctured, the selector 215₁₄ selects the information whose value is “0”. The data selected by the selector 215₁₄ is tied together with the data supplied from the selectors 215₈, 215₉, 215₁₀, 215₁₅ and 215₁₆, and supplied as selected received data and a priori probability information RAP to the received data and delaying-use data storage circuit 155.

[0416] The selector 215₁₅ selects, based on the number-of-input-bits information IN, either the data supplied from the selector 215₁₁ or the data supplied from the selector 215₁₂. More specifically, when the rate of the element encoder in the encoder 1 is denoted by “1/n” and the number-of-input-bits information IN indicates that the number of input bits is “1”, the selector 215₁₅ selects the data supplied from the selector 215₁₁. The data selected by this selector 215₁₅ is tied together with the data supplied from the selectors 215₈, 215₉, 215₁₀, 215₁₄ and 215₁₆, and supplied as selected received data and a priori probability information RAP to the received data and delaying-use data storage circuit 155.

[0417] The selector 215₁₆ selects, based on the number-of-input-bits information IN, either the data supplied from the selector 215₁₂ or the data supplied from the selector 215₁₃. More specifically, when the rate of the element encoder in the encoder 1 is denoted by “1/n” and the number-of-input-bits information IN indicates that the number of input bits is “1”, the selector 215₁₆ selects the data supplied from the selector 215₁₂. The data selected by this selector 215₁₆ is tied together with the data supplied from the selectors 215₈, 215₉, 215₁₀, 215₁₄ and 215₁₅, and supplied as selected received data and a priori probability information RAP to the received data and delaying-use data storage circuit 155.

[0418] The received value and a priori probability information selection circuit 154 can select the to-be-decoded received value TSR and extrinsic information or interleaved data TEXT by means of the selectors 215₁, 215₂, 215₃, 215₄, 215₅ and 215₆ to make a selection between the to-be-decoded received value TSR and extrinsic information or interleaved data TEXT as a code likelihood and appropriately select information which is to be entered for soft-output decoding. Also, with the selection by the selectors 215₈, 215₉, 215₁₀, 215₁₁, 215₁₂, 215₁₃ and 215₁₄, the received value and a priori probability information selection circuit 154 can substitute a symbol whose likelihood is “0” for a position where there exists no coded output.

[0419] The received data and delaying-use data storage circuit 155 includes a plurality of RAMs, control circuit and selection circuit (not shown). This received data and delaying-use data storage circuit 155 stores termination time information TPM and termination state information TSM supplied from the termination information generation circuit 153 and selected received value and a priori probability information RAP supplied from the received value and a priori probability information selection circuit 154.

[0420] Then, the received data and delaying-use data storage circuit 155 operates under the control of its the internal control circuit to select, by its selection circuit, predetermined information of the stored termination time information TPM and termination state information TSM, and outputs it as termination information TAL for use in the Iα computation circuit 158 and termination information TB0 and TB1 for use in the Iβ computation circuit 159. The termination information TAL is delayed a predetermined time, and supplied as termination information TALD to the Iα computation circuit 158. Also, the termination information TB0 and TB1 are delayed a predetermined time, and supplied as termination information TB0D and TB1D to the Iβ computation circuit 159.

[0421] Also, the received data and delaying-use data storage circuit 155 is controlled by its the internal control circuit to select, by its selection circuit, predetermined information of the stored selected received value and a priori probability information RAP, and outputs it as received data DA for use in the Iα computation circuit 158 and two sequences of received data DB0 and DB1 for use in the Iβ computation circuit 159. The received data DA is supplied to the Iγ computation circuit 156, while it is delayed a predetermined time, and supplied as delayed received data DAD to the received value or a priori probability information separation circuit 162. Also, the received data DB0 and DB1 are supplied to the Iγ computation circuit 156.

[0422] Note that the element decoder 50 makes so-called sliding windowing known as a means for processing sequential data. The present invention adopts the memory management method disclosed in the International Publication No. WO99/62183 of the Applicant's pending international patent application to manage the received data and delaying-use data storage circuit 155 and an Iβ storage circuit 160, which will be described in detail later, during the sliding windowing. The element decoder 50 will be described briefly herebelow. In the element decoder 50, received data punctuated at each predetermined length of discontinuation is read from the received data and delaying-use data storage circuit 155, a log likelihood Iβ is stored into the Iβ storage circuit 160, to thereby provide a memory management by which a log soft-output Iλ is eventually be obtained in due time sequence. However, the memory management is not done after computation of the log likelihood Iγ as set forth in the International Publication No. WO99/62183 but the received data is stored into the received data and delaying-use data storage circuit 155 and then the received data is read under an approximate memory management to compute the log likelihood Iγ.

[0423] Further the received data and delaying-use data storage circuit 155 can also store delaying data as will be described later. That is, this circuit 155 stores the received value TR and edge signal TEILS supplied from the edge detection circuit 80 to delay them the same time as taken by the soft-output decoding circuit 90 for its operation. The received data and delaying-use data storage circuit 155 supplies a delayed received value PDR resulted from the delaying of the received value TR as delayed received value SDR to the selectors 120₃ and 120₆. Also, this circuit 155 supplies a delayed edge signal PDIL resulted from the delaying of the edge signal TEILS as delayed edge signal SDILS to the selector 120₅.

[0424] The Iγ computation circuit 156 uses the received data DA, DB0 and DB1 supplied from the received data and delaying-use data storage circuit 155 to compute a log likelihood Iγ. More specifically, based on the notation set forth in the beginning of Section 2, the Iγ computation circuit 156 makes an operation as given by the following expression (48) for each received value y_t to compute a log likelihood Iγ at each time t. Note that the “sgn” in the expression (48) is a constant indicating the sign for positive or negative, that is, either “+1” or “−1”. In case the element decoder 50 is constructed as a system in which only negative values are handled as a log likelihood, the constant sgn takes “+1”. On the other hand, in case the element decoder 50 is constructed as a system in which only positive values are handled as a log likelihood, the constant sgn takes “−1”. That is, for each received value y_t, the Iγ computation circuit 156 computes a log likelihood Iγ logarithmically notated of a probability γ determined by the coded output pattern and received value or log likelihood Iγ whose positive/negative discriminate sign is reversed by logarithmically expressing the probability γ.
Iγ_t(m′,m)=sgn·(log(Pr{i_t=i(m′,m)})+log(Pr{y_t|x(m′,m)}))  (48)

[0425] Note that in the following, the element decoder 50 will be described as a system in which only negative or positive values is handled as a log likelihood as necessary. But unless otherwise specified, the constant sgn is “−1”, that is, the element decoder 50 is constructed as a system in which only positive values is handled as a log likelihood, and a positive value whose probability is higher will be denoted by a smaller value.

[0426] In this case, the Iγ computation circuit 156 computes a log likelihood Iγ based on the received value type information CRTY and a priori probability information type information CAPP and signal point mapping information CSIG (when the encoder 1 is to code data with TTCM or SCTCM) supplied from the control circuit 60, and the number-of-input-bits information IN and type information WM supplied from the code information generation circuit 151. The Iγ computation circuit 156 supplies the computed a log likelihood Iγ to the Iγ distribution circuit 157. That is, the Iγ computation circuit 156 supplies the log likelihood Iγ for use in the Iα computation circuit 158 as a log likelihood GA to the Iγ distribution circuit 157, while supplying the log likelihood Iγ for use in the Iβ computation circuit 159 as log likelihood GB0 and GB1 to the Iγ distribution circuit 157.

[0427] The Iγ computation circuit 156 can be implemented as a one including an Iβ0-computing Iγ computation circuit 220₁ to compute a log likelihood Iγ for use to compute a log likelihood Iβ0 of two sequences of log likelihood Iβ0 and Iβ1, an Iβ1-computing Iγ computation circuit 220₂ to compute a log likelihood Iγ for use to compute the log likelihood Iβ1, and an Iα-computing Iγ computation circuit 220₃ to compute a log likelihood Iγ for use to compute a log likelihood Iα, as shown in FIG. 33 for example. Since these an Iβ0-computing Iγ computation circuit 220₁, Iβ1-computing Iγ computation circuit 220₂ and Iα-computing Iγ computation circuit 220₃ can be implemented as a one having the same construction provided that input data to them are different from each other, only the Iβ0-computing Iγ computation circuit 220₁ will be described in the following with omission of the illustration and description of the Iβ1-computing Iγ computation circuit 220₂ and Iα-computing Iγ computation circuit 220₃.

[0428] The Iβ0-computing Iγ computation circuit 220₁ includes an information and code Iγ computation circuit 221 and Iγ normalization circuit 222.

[0429] Supplied with received data DB0 including the received value and a priori probability information, the information and code Iγ computation circuit 221 computes a log likelihood Iγ for all possible input/output patterns or a log likelihood Iγ for at least a part of the input/output patterns based on the received value type information CRTY, a priori probability information type information CAPP, signal point mapping information CSIG and number-of-input-bits information IN, as will be described in detail later.

[0430] At this time, in case the encoder 1 is not to code data with TTCM or SCTCM, the information and code Iγ computation circuit 221 computes, from the input received data DB0, sum of a priori probability information and so-called channel value as a log likelihood Iγ.

[0431] Also, in case the encoder 1 is to code data with TTCM or SCTCM, the information and code Iγ computation circuit 221 computes a log likelihood Iγ by computing an inner product of the input received data DB0. The reason is that the Euclidean distance in the I/Q plane is the log likelihood Iγ but since the transmission amplitude of output from the encoder takes a constant value in the PSK modulation, the determination of the Euclidean distance is equal to determination of the inner product.

[0432] The information and code Iγ computation circuit 221 supplies the thus computed log likelihood Iγ to the Iγ normalization circuit 222.

[0433] The Iγ normalization circuit 222 makes normalization for correction of uneven mapping of results of operations by the information and code Iγ computation circuit 221 as will be described in detail later. More particularly, the Iγ normalization circuit 222 makes a predetermined operation of each log likelihood to match a one, corresponding to data whose probability is maximum, of a plurality of log likelihood Iγ computed by the information and code Iγ computation circuit 221 with a log likelihood corresponding to the possible maximum probability. That is, in case the element decoder 50 handles the log likelihood as a negative value, the Iγ normalization circuit 222 makes normalization by adding a predetermined value to each of the plurality of log likelihood Iγ to match a one, having a maximum value, of the plurality of log likelihood Iγ computed by the information and code Iγ computation circuit 221 with a maximum value which the element decoder 50 can express. Also, in case the element encoder 50 is to handle the log likelihood as a positive value, the Iγ normalization circuit 222 makes normalization by subtracting a predetermined value from each of the plurality of log likelihood Iγ to match a one, having a minimum value, of the plurality of log likelihood Iγ computed by the information and code Iγ computation circuit 221 with a minimum value which the element decoder 50 can express. The Iγ normalization circuit 222 clips the normalized log likelihood Iγ according to a necessary dynamic range, and supplies it as a log likelihood GB0 to the Iγ distribution circuit 157.

[0434] The Iβ0-computing Iγ computation circuit 220₁ computes a log likelihood Iγ for use to compute the log likelihood Iβ0, and supplies it as likelihood GB0 to the Iγ distribution circuit 157.

[0435] Also, the Iβ1-orientded Iγ computation circuit 220₂ is supplied with the received data DB1 instead of the received data DB0 supplied to the Iβ0-computing Iγ computation circuit 220₁ to make a similar operation to that made by the Iβ0-computing Iγ computation circuit 220₁. The Iβ1-computing Iγ computation circuit 220₂ computes a log likelihood Iγ for use to compute a log likelihood Iβ1, and supplies it as a log likelihood GB1 to the Iγ distribution circuit 157.

[0436] Similarly, the Iα-computing Iγ computation circuit 220₃ is supplied with the received data DA instead of the received data DB0 supplied to the Iβ0-computing Iγ computation circuit 220₁ to make a similar operation to that made by the Iβ0-computing Iγ computation circuit 220₁. The Iα-computing Iγ computation circuit 220₃ computes a log likelihood Iα for use to compute log likelihood Iα, and supplies it as a log likelihood GA to the Iγ distribution circuit 157.

[0437] The Iγ computation circuit 156 uses the received data DA, DB0 and DB1 to generate log likelihood GA, GB0 and GB1 computed as a log likelihood Iγ, and supplies these likelihood GA, GB0 and GB1 to the Iγ distribution circuit 157.

[0438] As will be described in detail later, the Iγ distribution circuit 157 distributes each of the log likelihood GA, GB0 and GB1 supplied from the Iγ computation circuit 156 correspondingly to the configuration of a code. That is, the Iγ distribution circuit 157 distributes the log likelihood GA, GB0 and GB1 to correspond to the trellis branches corresponding to the configuration of the code. At this time, the Iγ distribution circuit 157 distributes the log likelihood GA, GB0 and GB1 on the basis of the generator matrix information CG supplied from the control circuit 60, and number-of-input-bits information IN, type information WM, number-of-memories information MN and branch input/output information BIO supplied from the code information generation circuit 151.

[0439] Also, the Iγ distribution circuit 157 has a function to tie parallel paths, if any, on the trellis when decoding a code whose parallel paths exist on the trellis.

[0440] The Iγ distribution circuit 157 supplies a log likelihood Iγ obtained via the distribution to the Iγ computation circuit 158 and Iγ computation circuit 159. Namely, the Iγ distribution circuit 157 supplies the log likelihood Iγ for use in the Iα computation circuit 158 and log likelihood DGA to the Iα computation circuit 158, while supplying the log likelihood Iγ for use in the Iβ computation circuit 159 as log likelihood DGB0 and DGB1 to the Iβ computation circuit 159. Also, the Iγ distribution circuit 157 supplies the log likelihood Iγ obtained with there parallel paths not being tied together as a log likelihood DGAB to the Iα computation circuit 158 as will further be described later.

[0441] More particularly, as shown in FIG. 34 for example, the Iγ distribution circuit 157 can be implemented as a one including a branch input/output information computation circuit 223 to compute input/output information on the trellis branches corresponding to the configuration of a code to be decoded, an Iβ0-computing Iγ distribution circuit 224₁ to distribute a log likelihood Iγ, for use to compute a log likelihood Iβ0, of two sequences of log likelihood Iβ0 and Iβ1, an Iβ1-computing Iγ distribution circuit 224₂ to distribute a log likelihood Iγ for use to compute a log likelihood Iβ1, an Iα-computing Iγ distribution circuit 224₃ to distribute a log likelihood Iγ for use to compute a log likelihood Iα, an Iβ0-computing parallel path processing circuit 225₁ to process parallel paths for use to compute a log likelihood Iβ0 when parallel paths exist in the trellis, an Iβ1-computing parallel path processing circuit 225₂ to process parallel paths for use to compute a log likelihood Iβ1 when parallel paths exist in the trellis, and an Iα-computing parallel path processing circuit 225₃ to process parallel paths for use to compute a log likelihood Iα when parallel paths exist in the trellis.

[0442] Based on the generator matrix information CG, number-of-input-bits information IN, type information WM, number-of-memories information MN and branch input/output information BIO, the branch input/output information computation circuit 223 identifies the configuration of a code, and computes branch input/output information in a sequence opposite to the time base of the trellis branch corresponding to the configuration of the code. The branch input/output information computation circuit 223 supplies the thus computed branch input/output information BI to the Iβ0-computing Iγ distribution circuit 224₁ and Iβ1-computing Iγ distribution circuit 224₂.

[0443] Supplied with the log likelihood GB0, the Iβ0-computing Iγ distribution circuit 224₁ makes a distribution corresponding to the configuration of the code on the basis of the branch input/output information BI, and supplies the log likelihood PGB0 obtained via the distribution to the Iβ0-computing parallel path processing circuit 225₁.

[0444] Supplied with the log likelihood GB1, the Iβ1-computing Iγ distribution circuit 224₂ makes a distribution corresponding to the configuration of the code on the basis of the branch input/output information BI, and supplies the log likelihood PGB1 obtained via the distribution to the Iβ1-computing parallel path processing circuit 225₂.

[0445] Supplied with the log likelihood GA, the Iα-computing Iγ distribution circuit 224₃ makes a distribution corresponding to the configuration of the code on the basis of the branch input/output information BIO, and supplies the log likelihood PGA obtained via the distribution to the Iα-computing parallel path processing circuit 225₃. Also, it supplies the log likelihood PGA obtained via the distribution as a log likelihood DGAB to the Iα computation circuit 158.

[0446] As will be described in detail later, when supplied with the log likelihood PGB0 which correspond to the parallel paths, the Iβ0-computing parallel path processing circuit 225₁ ties the log likelihood PGB0 and outputs the data as likelihood Iγ for use to compute the log likelihood DGB0, that is, log likelihood Iβ0. Also, the Iβ0-computing parallel path processing circuit 225₁ outputs the input log likelihood PGB0 as it is as a log likelihood DGB0 when the log likelihood PGB0 does not correspond to the parallel paths. At this time, the Iβ0-computing parallel path processing circuit 225₁ selects to-be-outputted log likelihood DGB0 based on the number-of-input-bits information IN.

[0447] More particularly, the Iβ0-computing parallel path processing circuit 225₁ includes a maximum number of parallel path-computing log-sum operation circuits 226_n, the maximum number corresponding to the number of states of a code to be decoded, and a selector 227 to make a 2-to-1 selection, as shown in FIG. 35. The Iβ0-computing parallel path processing circuit 225₁ is defined herein as a one which decodes one of codes whose parallel paths exist in the trellis, denoted by a trellis having a maximum of 32 branches and which has a maximum of four states, more specifically, a code having parallel paths of which eight paths arriving at each of four states. The Iβ0-computing parallel path processing circuit 225₁ includes 16 parallel path-computing log-sum operation circuits 226₁, 226₂, 226₃, . . . , 226₁₆ to transform the 32 branches to sixteen log likelihood Iγ.

[0448] As will be seen from FIG. 36, the parallel path-computing log-sum operation circuit 226₁ includes two differentiators 229₁ and 229₂, three selectors 230, 231 and 233, a selection control signal generation circuit 232 to generate a control signal for use to control the selecting operation of these selectors 230, 231 and 233, a lookup table 234 composed of ROM (read-only memory) to store, as a table, values of a correction term in the so-called log-sum correction, and an adder 235. Of these elements, the differentiators 229₁ and 229₂, selectors 230 and 231 and the selection control signal generation circuit 232 form together a comparison and absolute value computation circuit 228.

[0449] The comparison and absolute value computation circuit 228 is to compare two input data to see which of the data is larger or smaller and compute the absolute value of a difference between the two data.

[0450] The differentiator 229₁ computes a difference between log likelihood PG00 and PG01 being two log likelihood Iγ of the log likelihood PGB0 of a set of 32 kinds of log likelihood Iγ. More strictly, on the assumption that the likelihood PG00 and PG01 are of 9 bits, respectively, for example, the differentiator 229₁ computes a difference between the MSB of data of lower 6 bits of the likelihood PG00, to which “1” is added, and the MSB of data of lower 6 bits of the likelihood PG01, to which “0” is added. The differentiator 229₁ supplies the thus computed difference DA1 to the selector 230 and selection control signal generation circuit 232.

[0451] The differentiator 229₂ computes a difference between the log likelihood PG01 and PG00. More strictly, on the assumption that the likelihood PG00 and PG01 are of 9 bits, respectively, for example, the differentiator 229₂ computes a difference between the MSB of data of lower 6 bits of the likelihood PG01, to which “1” is added, and the MSB of data of lower 6 bits of the likelihood PG00, to which “0” is added. The differentiator 229₂ supplies the thus computed difference DA0 to the selector 230 and selection control signal generation circuit 232.

[0452] Based on a control signal SL1 supplied from the selection control signal generation circuit 232, the selector 230 selects a difference DA1 supplied from the differentiator 229₁ or a difference DA0 supplied from the differentiator 229₂, whichever is larger. The selector 230 supplies data CA obtained via the selection to the selector 231.

[0453] The selector 231 selects, based on a control signal SL2 supplied from the selection control signal generation circuit 232, the data CA supplied from the selector 230 or the data having a predetermined value, whichever is larger. More specifically, since the value of the correction terminal for the difference supplied as the data CA is asymptotic to a predetermined value M, the selector 231 selects data having a predetermined value M when the value of the data CA exceeds the predetermined value M. The selector 231 supplies data DM obtained via the selection to the lookup table 234.

[0454] The selection control signal generation circuit 232 generates, based on the log likelihood PG00 and PG01 and the differences DA1 and DA0, a control signal SL1 which is used to control the selecting operation of the selectors 230 and 233, and also a control signal SL2 under which the selecting operation of the selector 231 is controlled. At this time, the selection control signal generation circuit 232 separates upper and lower bits of a metric based on the log likelihood PG00 and PG01 to generate the control signals SL1 and SL2 which indicate a selection decision statement, which will further be described later.

[0455] The comparison and absolute value computation circuit 228 constructed as above computes an absolute value of a difference between the log likelihood PG00 and PG01. At this time, it is assumed in the comparison and absolute value computation circuit 228 that in case the log likelihood PG00 and PG01 include 9 bits, respectively, for example, the MSB of data of lower 6 bits of the log likelihood PG00, having “1” added thereto, and MSB of data of lower 6 bits of the log likelihood PG01, to which “0” is added, are supplied to the differentiator 229₁, as will be described in detail later. Similarly, the differentiator 229₂ in the comparison and absolute value computation circuit 228 is supplied with the MSB of data of lower 6 bits of the log likelihood PG00, having “0” added thereto, and MSB of data of lower 6 bits of the log likelihood PG01, to which “1” is added. That is, the differentiators 229₁ and 229₂ are supplied with the MSB of data of lower 6 bits of the log likelihood PG00 or PG01, having “1” or “0” added thereto, which is intended for a higher-speed comparison in size between the log likelihood PG00 and PG01 and involved in the generation of a selection decision statement by separating upper and lower bits of a metric by the selection control signal generation circuit 232. This will be described in detail later.

[0456] The selector 233 selects, based on the control signal SL1 supplied from the selection control signal generation circuit 232, the log likelihood PG00 or PG01, whichever is smaller in value. The selector 233 supplies data SPG obtained via the selection to the adder 235.

[0457] The lookup table 234 stores, as a table, values of the correction term in the log-sum correction. It reads, from the table, a value of the correction term corresponding to the data DM supplied from the selector 231, and supplies it as data RDM to the adder 235.

[0458] The adder 235 adds data SPG supplied from the selector 233 and data RDM supplied from the lookup table 234 to compute the log likelihood Iγ. The adder 235 supplies the thus computed log likelihood Iγ as a log likelihood PPG00 to the selector 227.

[0459] The parallel path-computing log-sum operation circuit 226₁ ties together the two log likelihood PG00 and PG01 corresponding to the parallel paths, and supplies the data as a log likelihood PPG00 to the selector 227.

[0460] The parallel path-computing log-sum operation circuit 226₂ is constructed similarly to the parallel path-computing log-sum operation circuit 226₁ to tie together two likelihood PG02 and PG03 corresponding to the parallel paths and supply the data as likelihood PPG01 to the selector 227.

[0461] Also, the parallel path-computing log-sum operation circuit 226₃ is constructed similarly to the parallel path-computing log-sum operation circuit 226₁ to tie together two likelihood PG04 and PG05 corresponding to the parallel paths and supply the data as likelihood PPG02 to the selector 227.

[0462] Also, the parallel path-computing log-sum operation circuit 226₁₆ is constructed similarly to the parallel path-computing log-sum operation circuit 226₁ to tie together two likelihood PG030 and PG031 corresponding to the parallel paths and supply the data as likelihood PPG15 to the selector 227.

[0463] Each of the plurality of parallel path-computing log-sum operation circuits 226_n ties two likelihood corresponding to the parallel paths. The log likelihood PPG00, PPG01, PPG02, . . . , PPG15 tied together by each of the parallel path-computing log-sum operation circuits 226_n are supplied as likelihood PPG to the selector 227.

[0464] In the Iβ0-computing parallel path processing circuit 225₁, the selector 227 selects, based on the number-of-input bits information IN, either a one of the log likelihood PGB0 supplied from the Iβ0-computing Iγ distribution circuit 224₁ and which corresponds to a lower metric or a likelihood PPG supplied from each of the parallel path-computing log-sum operation circuits 226_n. More particularly, the selector 227 selects the log likelihood PPG in case the element encoder in the encoder 1 is destined to code a code whose parallel paths exist in the trellis. Note that the number-of-input-bits information IN is used herein as a control signal to control the selecting operation of the selector 227 but actually the selector 227 is supplied with a control signal which indicates whether there exists a code whose parallel paths exist in the trellis.

[0465] In the Iβ0-computing parallel path processing circuit 225₁, when the log likelihood PGB0 supplied thereto corresponds to parallel paths, the selector 227 selects tied log likelihood PPG to combine the log likelihood PPG and a one of the log likelihood PGB0 which corresponds to the upper metric, and supplies the data as a log likelihood DGB0 to the Iβ computation circuit 159. Also, when the input log likelihood PGB0 does not correspond to the parallel paths, the Iβ0-computing parallel path processing circuit 225₁ outputs the log likelihood PGB0 as it is as likelihood DGB0.

[0466] The Iβ1-computing parallel path processing circuit 225₂ is constructed similarly to the Iβ0-computing parallel path processing circuit 225₁. So, it will not be described in detail herein. In this Iβ1-computing parallel path processing circuit 225₂, when the log likelihood PGB1 supplied thereto corresponds to the parallel paths, the log likelihood PGB1 is tied and supplied as a log likelihood DGB1, that is, log likelihood Iγ for use to compute a log likelihood Iβ1, to the Iβ computation circuit 159. Also, when the input log likelihood PGB1 does not correspond to the parallel paths, the Iβ1-computing parallel path processing circuit 225₂ supplies the log likelihood PGB1 as it is as a log likelihood DGB1 to the Iβ computation circuit 159.

[0467] Also, the Iα-computing parallel path processing circuit 225₃ is constructed similarly to the Iβ0-computing parallel path processing circuit 225₁, and so it will not be described in detail herein. In this Iα-computing parallel path processing circuit 225₃, when the log likelihood PGA supplied thereto corresponds to the parallel paths, the log likelihood PGA is tied and supplied as a log likelihood DGA, that is, log likelihood Iγ for use to compute a log likelihood Iα, to the Iα computation circuit 158. Also, when the input log likelihood PGA does not correspond to the parallel paths, the Iα-computing parallel path processing circuit 225₃ supplies the log likelihood PGA as it is as a log likelihood DGA to the Iα computation circuit 158.

[0468] The Iγ distribution circuit 157 distributes the log likelihood GA, GB0 and GB1 each correspondingly to the configuration of a code. For decoding a code whose parallel paths exist in the trellis, the Iγ distribution circuit 157 ties the parallel paths and supplies the thus obtained log likelihood DGA and DGAB to the Iα computation circuit 158, while supplying the thus obtained log likelihood DGB0 and DGB1 to the Iβ computation circuit 159.

[0469] The Iα computation circuit 158 uses the log likelihood DGA and DGAB supplied from the Iγ distribution circuit 157 to compute a log likelihood Iα. Specifically, according to the notation set forth in the beginning of Section 2, the Iα computation circuit 158 uses a log likelihood Iγ to make an operation given by the following expression (49) for computation of a log likelihood Iα at each time t. Note that the operator “#” in the expression (49) indicates the so-called log-sum operation, namely, a log-sum operation for a log likelihood at a transition of an input “1” from the state m″ to state m and log likelihood at a transition of an input “0” from the state m″ to state m. More specifically, the Iα computation circuit 158 makes an operation given by the following expression (50) when the constant sgn is “+1”,while making an operation given by the following expression (51) when the constant sgn is “−1”, thereby computing the log likelihood Iα at each time t. That is, the Iα computation circuit 158 computes, based on the log likelihood Iγ, a log likelihood Iα logarithmically notated of a probability a in which for each received value y_t, paths run to each state from a coding start state in time sequence or log likelihood Iα whose positive/negative discriminate sign is inverted by logarithmically expressing the probability α.

[0470] $\begin{array}{cc}I{\alpha }_t\left(m\right)=\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right)\right)\#\left(I{\alpha }_{t-1}\left(m^{″}\right)+I{\gamma }_t\left(m^{″},m\right)\right)& \left(49\right)\\ I{\alpha }_t\left(m\right)=\max \left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right),I{\alpha }_{t-1}\left(m^{″}\right)+I{\gamma }_t\left(m^{″},m\right)\right)+\log \left(1+e^{-\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right)\right)-\left(I{\alpha }_{t-1}\left(m^{″}\right)+I{\gamma }_t\left(m^{″},m\right)\right)}\right)& \left(50\right)\\ I{\alpha }_t\left(m\right)=\min \left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right),I{\alpha }_{t-1}\left(m^{″}\right)+I{\gamma }_t\left(m^{″},m\right)\right)-\log \left(1+e^{-\left(I{\alpha }_{t-1}\left(m^{\prime }\right)+I{\gamma }_t\left(m^{\prime },m\right)\right)-\left(I{\alpha }_{t-1}\left(m^{″}\right)+I{\gamma }_t\left(m^{″},m\right)\right)}\right)& \left(51\right)\end{array}$