Patent Number: 
Section: description

(A) Turbo Codes The MAP decoding method manifests its effectiveness in turbo codes. FIG. 1 is a block diagram of a communication system that includes a turbo encoder and a turbo decoder. Numeral 11 denotes the turbo encoder, which is provided on the data transmitting side, and numeral 12 denotes the turbo decoder, which is provided on the data receiving side. Numeral 13 denotes a data communication path. Further, character u represents transmit information data of length N; xa, xb, xc represent encoded data obtained by encoding the information data u by the turbo encoder 11; ya, yb, yc denote receive signals that have been influenced by noise and fading as a result of propagation of the encoded data xa, xb, xc through the communication path 13; and uxe2x80x2 represents results of decoding obtained by decoding the receive data ya, yb, yc by the turbo decoder 12. These items of data are as expressed below. The turbo encoder 11 encodes the information data u of information length N and outputs the encoded data xa, xb, xc. The encoded data xa is the information data u per se, the encoded data xb is data obtained by the convolutional encoding of the information data u by an encoder ENC1, and the encoded data xc is data obtained by the interleaving (xcfx80) and convolutional encoding of the information data u by an encoder ENC2. In other words, a turbo code is obtained by combining two convolutional codes. It should be noted that an interleaved output xaxe2x80x2 differs from the encoded data xa only in terms of its sequence and therefore is not output. FIG. 2 is a diagram showing the details of the turbo encoder 11. Numerals 11a, 11b denote convolutional encoders (ENC1, ENC2) that are identically constructed, and numeral 11c denotes an interleaving unit (xcfx80). The convolutional encoders 11a, 11b, which are adapted to output recursive systematic convolutional codes, are each constructed by connecting two flip-flops FF1, FF2 and three exclusive-OR gates EXOR1xcx9cEXOR3 in the manner illustrated. The flip-flops FF1, FF2 take on four states O(=00), 1(=10), 2(=01), 3(=11). If 0 or 1 is input in each of these states, the states undergo a transition as illustrated in FIG. 3 and the flip-flops output xa, xb. In FIG. 3, the left side indicates the state prior to input of receive data, the right side the state after the input, the solid lines the path of the state transition when xe2x80x9c0xe2x80x9d is input and the dashed lines the path of the state transition when xe2x80x9c1xe2x80x9d is input, and 00, 11, 10, 01 on the paths indicate the values of the output signals xa, xb. By way of example, if xe2x80x9c0xe2x80x9d is input in the state 0(=00), the output is 00 and the state becomes 0(=00); if xe2x80x9c1xe2x80x9d is input, the output is 11 and the state becomes 1(=10). FIG. 4 is a block diagram of the turbo decoder. Turbo decoding is performed by a first element decoder DEC1 using ya and yb first among the receive signals ya, yb, yc. The element decoder DEC1 is a soft-output element decoder and outputs the likelihood of decoded results. Next, similar decoding is performed by a second element decoder DEC2 using the likelihood, which is output from the first element decoder DEC1, and yc. That is, the second element decoder DEC2 also is a soft-output element decoder and outputs the likelihood of decoded results. Here yc is a receive signal corresponding to xc, which was obtained by interleaving and encoding the information data u. Accordingly, the likelihood that is output from the first element decoder DEC1 is interleaved (xcfx80) before it enters the second element decoder DEC2. The likelihood output from the second element decoder DEC2 is deinterleaved (xcfx80xe2x88x921) and then is fed back as the input to the first element decoder DEC1. Further, uxe2x80x2 is decoded data (results of decoding) obtained by rendering a xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d decision regarding the interleaved results from the second element decoder DEC2. Error rate is reduced by repeating the above-described decoding operation a prescribed number of times. MAP element decoders can be used as the first and second element decoders DEC1, DEC2 in such a turbo element decoder. (B) First Embodiment (a) Operation Sequence FIG. 5 is a diagram useful in describing the operation sequence of a first MAP decoding method according to the present invention. (1) At the beginning, all backward probabilities xcex2k(m) (k=N to 1) are calculated in the reverse direction up to a first backward probability at k=1 starting from an Nth backward probability at k=N, and (2) an m1th backward probability xcex2m1(m) to a first backward probability xcex21(m) are saved. Next, (3) first forward probabilities xcex111(m), xcex101(m) are calculated, first decoded data ui and likelihood L (ui) are obtained using the first forward probabilities and the saved first backward probability xcex21(m), and second to m1th decoded data u2 to um1 and likelihoods L (u2) to L (um1) are obtained in similar fashion. (4) Thereafter, backward probabilities are calculated in the reverse direction from the Nth backward probability to an (m1+1)th backward probability, and (5) an m1th backward probability xcex2m2(m) to the (m1+1)th backward probability xcex2m1+1(m) are saved. Next, (6) (m1+1)th forward probabilities xcex11m1+1(m), xcex10m1+1(m) are calculated, (m1+1)th decoded data um1+1 and likelihood L (um1+1) are obtained using the (m1+1)th forward probabilities and the saved (m1+1)th backward probability xcex2m1+1(m), and (m1+2)th to m2th decoded data um1+2 to um2 and likelihoods L (um1+2) to L (um2) are obtained in similar fashion. (7) Thereafter, (m2+1)th to Nth decoded data um2+1 to uN and likelihoods L (um2+1) to L (uN) are obtained in similar fashion. (b) MAP Decoder of First Embodiment FIG. 6 is a block diagram of a MAP decoder according to the first embodiment. A MAP controller 50 controls the overall MAP decoder, i.e., controls the calculation timing of each component and the read-out and writing of data from and to memory, etc., in accordance with the operation sequence of FIG. 5. An input/output interleaver 51, which is for changing the output sequence of receive data as appropriate, has a memory for storing all receive data and a data output unit for outputting the receive data in an order that is the reverse of or the same as that in which the data was input. With a turbo decoder, it is necessary to interleave the receive data and therefore the decoder has a memory for storing all receive data. This means that this memory for interleaving can also be used as the memory of the input/output interleaver 51. Hence there is no burden associated with memory. A shift-probability calculation unit 52 uses receive data (yak,ybk) at time k (=N) to calculate the following: probability xcex30,k that (xak,xbk) is (0,0) probability xcex31,k that (xak,xbk) is (0,1) probability xcex32,k that (xak,xbk) is (1,0) probability xcex33,k that (xak,xbk) is (1,1) Further, a backward-probability calculation unit 53 calculates the backward probability xcex2kxe2x88x921(m) (m=0 to 3) in each state m (=0 to 3) at time kxe2x88x921 using the backward probability xcex2k(m) and shift probability xcex3s,k (s=0, 1, 2, 3) at time k (=N). Thereafter, the shift-probability calculation unit 52 and backward-probability calculation unit 53 repeat the above-described calculations at k=kxe2x88x921, perform the calculations from k=N to k=1 and save the m1th backward probability xcex2m1(m) to the first backward probability xcex21(m) from k=m1 to 1 in a memory 54. Thereafter, the shift-probability calculation unit 52 uses receive data (yak,ybk) at time k (=1) to calculate the following: probability xcex30,k that (xak,xbk) is (0,0) probability xcex31,k that (xak,xbk) is (0,1) probability xcex32,k that (xak,xbk) is (1,0) probability xcex33,k that (xak,xbk) is (1,1) Further, the forward-probability calculation unit 55 assumes k=1 and calculates the forward probabilities xcex11k(m), xcex10k(m) in each state m (=0 to 3) at time k using the forward probabilities xcex11kxe2x88x921(m), xcex10kxe2x88x921(m) at time (kxe2x88x921) and the obtained shift probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k at time k. A joint-probability calculation unit 56 multiplies the forward probability xcex11k(m) and backward probability xcex2k(m) in each state m (=0 to 3) at time k to calculate the probability xcex1k(m) that the kth item of original data uk is xe2x80x9c1xe2x80x9d, and similarly calculates the probability xcex0k(m) that the original data uk is xe2x80x9c0xe2x80x9d using the forward probability xcex10k(m) and backward probability xcex2k(m) in each state m (=0 to 3) at time k. A uk and uk likelihood calculation unit 57 obtains the sum total xcexa3mxcex0k(m) of the probabilities of xe2x80x9c0xe2x80x9d and the sum total xcexa3mxcex1k(m) of the probabilities of xe2x80x9c1xe2x80x9d in each state m (=0 to 3) at time k and outputs the likelihood in accordance with the following equation: L(u)=log [xcexa3mxcex1k(m)/xcexa3mxcex0k(m)] Further, the decoded result uk=1 is output if L(u) greater than 0 holds and the decoded result uk=0 is output if L(u) less than 0 holds. Thereafter, the shift-probability calculation unit 52, a forward-probability calculation unit 55, the joint-probability calculation unit 56 and the uk and uk likelihood calculation unit 57 repeat the foregoing calculations at k=k+1, perform the calculations from k=1 to k=m1, calculate uk and the confidence (likelihood) L(uk) thereof at each time from k=1 to m1 and output the same. If the calculation of uk and L(uk) from k=1 to k=m1 is completed, then, under the control of the MAP controller 50, the shift-probability calculation unit 52 calculates the probabilities xcex3hd 0,k, xcex31,k, xcex32,k, xcex33,k using the receive data (yak,ybk) at time k (=N). Further, the backward-probability calculation unit 53 calculates the backward probability xcex2kxe2x88x921(m) (m=0 to 3) in each state m (=0 to 3) at time kxe2x88x921 using the backward probability xcex2k(m) and shift probability xcex3s,k (s=0 1, 2, 3) at time k=(N). The shift-probability calculation unit 52 and backward-probability calculation unit 53 subsequently repeat the above calculations at k=kxe2x88x921, perform calculations from k=N to k=m1+1 and save the m2th backward probability xcex2m2(m) to the (m1+1)th backward probability xcex2m1+1(m) from k=m2 to m1+1 in a memory 54. The shift-probability calculation unit 52 subsequently calculates the probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k using the receive data (yak,ybk) at time k (=m1+1). Further, the forward-probability calculation unit 53 assumes k=m1+1 and calculates the forward probabilities xcex11k(m), xcex10k(m), in each state m (=0 to 3) at time k using the forward probabilities xcex11kxe2x88x921(m), xcex10kxe2x88x921(m) at time (kxe2x88x921) and the obtained shift probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k at time k. The joint-probability calculation unit 56 and the uk and uk likelihood calculation unit 57 perform operations similar to those described above and output uk and the likelihood L(uk). Thereafter, the shift-probability calculation unit 52, forward-probability calculation unit 55, joint-probability calculation unit 56 and the uk and uk likelihood calculation unit 57 repeat the foregoing calculations at k=k+1, perform the calculations from k=m1+1 to k=m2, calculate uk and the confidence (likelihood) L(uk) thereof at each time from k=m1+1 to m2 and output the same. If the above operations are completed, then (m2+1)th to Nth decoded data um2+1 to uN and likelihoods L(um2+1) to L(uN) are subsequently obtained in similar fashion. In accordance with the first aspect of the present invention, just rxc3x97m (number of states) of memory capacity is needed to store backward probabilities in a case where m1=r, m2=2 r, m3 =3 r . . . holds. Moreover, since the backward probabilities are calculated from k=N at all times, backward probability xcex2k(m) is calculated accurately to make it possible to raise the precision of MAP decoding. (C) Second Embodiment (a) Operation Sequence FIG. 7 is a diagram useful in describing the operation sequence of a second MAP decoding method according to the present invention. (1) At the beginning, all backward probabilities xcex2k(m) (k=N to 1) are calculated in the reverse direction up to a first backward probability at k=1 starting from an Nth backward probability at k=N, an msth backward probability xcex2ms(m), m(sxe2x88x921)th backward probability xcex2m(sxe2x88x921)(m), . . . , m3th backward probability xcex2m3(m), m2th backward probability xcex2m2(m) are saved discretely and an m1th backward probability xcex2m1(m) to a first backward probability xcex21(m) are saved continuously. (2) Next, first forward probabilities xcex111(m), xcex101(m) are calculated, first decoded data u1 and likelihood L(u1) are obtained using the first forward probabilities and the saved first backward probability xcex21(m), and second to m1th decoded data u2 to um1 and likelihoods L(u2) to L(um1) are obtained in similar fashion. (3) Thereafter, backward probabilities up to a (m1+1)th backward probability xcex2m1+1(m) are calculated and stored starting from the saved m2th backward probability xcex2m2(m). (4) Next, (m1+1)th forward probabilities xcex11m1+1(m), xcex10m1+1(m) are calculated, (m1+1)th decoded data um1+1 and likelihood L (um1+1) are obtained using the (m1+1)th forward probabilities and the saved (m1+1)th backward probability xcex2m1+1(m), and (m1+2)th to m2th decoded data um1+2 to um2 and likelihoods L(um1+2) to L(um2) are obtained in similar fashion. (5) Thereafter, backward probabilities up to a (m2+1)th backward probability xcex2m2+1(m) are calculated and stored starting from the saved m3th backward probability xcex2m3(m). (6) Next, (m2+1)th forward probabilities xcex11m2+1(m), xcex10m2+1(m) are calculated, (m2+1)th decoded data um2+1 and likelihood L (um2+1) are obtained using the (m2+1)th forward probabilities and the saved (m2+1)th backward probability xcex2m2+1(m), and (m2+2)th to m3th decoded data um2+2 to um3 and likelihoods L(um2+2) to L(um3) are obtained in similar fashion. (7) Thereafter, and in similar fashion, (m3+1)th to Nth decoded data um3+1 to uN and likelihoods L(um3+1) to L(uN) are obtained using the saved m4th backward probability xcex2m4(m), . . . , m(sxe2x88x921)th backward probability xcex2m(sxe2x88x921), msth backward probability xcex2ms(m). (b) MAP Decoder of Second Embodiment FIG. 8 is a block diagram of a MAP decoder according to the second embodiment, in which components identical with those shown in FIG. 6 are designated by like reference characters. The MAP controller 50 controls the overall MAP decoder, i.e., controls the calculation timing of each component and the read-out and writing of data from and to memory, etc., in accordance with the operation sequence of FIG. 7. The input/output interleaver 51, which is for changing the output sequence of receive data as appropriate, has a memory for storing all receive data and a data output unit for outputting the receive data in an order that is the reverse of or the same as that in which the data was input. The shift-probability calculation unit 52 uses receive data (yak, ybk) at time k (=N) to calculate the following: probability xcex30,k that (xak,xbk) is (0,0) probability xcex31,k that (xak,xbk) is (0,1) probability xcex32,k that (xak,xbk) is (1,0) probability xcex33,k that (xak,xbk) is (1,1) Further, a backward-probability calculation unit 53 calculates the backward probability xcex2kxe2x88x921(m) (m=0 to 3) in each state m (=0 to 3) at time kxe2x88x921 using the backward probability xcex2k(m) and shift probability xcex3s,k (s=0, 1, 2, 3) at time k (=N). Thereafter, the shift-probability calculation unit 52 and backward-probability calculation unit 53 repeat the above-described calculations at k=kxe2x88x921 and perform the calculations from k=N to k=1. The backward-probability calculation unit 53 stores the msth backward probability xcex2ms(m), m(sxe2x88x921)th backward probability xcex2msxe2x88x921(m), . . . , m3th backward probability xcex2m3(m), m2th backward probability xcex2m2(m), which are obtained discretely in concurrence with the calculation of backward probabilities from k=N to 1, in a discrete backward probability storage section 54a of memory 54, and stores the m1th backward probability xcex2m1(m) to the first backward probability xcex21(m) in a continuous backward probability storage section 54b.  The shift-probability calculation unit 52 subsequently uses the receive data (yak,ybk) at time k (=1) to calculate the following: probability xcex30,k that (xak,xbk) is (0,0) probability xcex31,k that (xak,xbk) is (0,1) probability xcex32,k that (xak,xbk) is (1,0) probability xcex33,k that (xak,xbk) is (1,1) Further, the forward-probability calculation unit 55 assumes k=1 and calculates the forward probabilities xcex11k(m), xcex10k(m) at time k using the forward probabilities xcex11kxe2x88x921(m), xcex10kxe2x88x921(m) at time (kxe2x88x921) and the obtained shift probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k at time k. The joint-probability calculation unit 56 multiplies the forward probability xcex11k(m) and backward probability xcex2k(m) in each state m (=0 to 3) at time k to calculate the probability xcex1k(m) that the kth item of original data uk is xe2x80x9c1xe2x80x9d, and similarly calculates the probability xcex0k(m) that the original data uk is xe2x80x9c0xe2x80x9d using the forward probability xcex10k(m) and backward probability xcex2k(m) in each state m (=0 to 3) at time k. A uk and uk likelihood calculation unit 57 obtains sum total xcexa3mxcex0k(m) of the probabilities of xe2x80x9c0xe2x80x9d and the sum total xcexa3mxcex1k(m) of the probabilities of xe2x80x9c1xe2x80x9d in each state m (=0 to 3) at time k and outputs the likelihood in accordance with the following equation: L(u)=log [xcexa3mxcex1k(m)/xcexa3mxcex0k(m)] Further, the decoded result uk=1 is output if L(u) greater than 0 holds and the decoded result uk=0 is output if L(u) less than 0 holds. Thereafter, the shift-probability calculation unit 52, forward-probability calculation unit 55, joint-probability calculation unit 56 and uk and uk likelihood calculation unit 57 repeat the foregoing calculations at k=k+1, perform the calculations from k=1 to k=m1, calculate uk and the confidence (likelihood) L(uk) thereof at each time from k=1 to m1 and output the same. If the calculation of uk and L(uk) from k=1 to k=m1 is completed, then, under the control of the MAP controller 50, the shift-probability calculation unit 52 calculates the probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k using the receive data (yak,ybk) at time k (=m2). Further, the backward-probability calculation unit 53 reads the backward probability xcex2k(m) [=xcex2m2(m)] at time k (=m2) out of the storage section 54a, calculates the backward probability xcex2kxe2x88x921(m) (m=0 to 3) in each state m (=0 to 3) at time kxe2x88x921 using the backward probability xcex2k(m) and shift probability xcex3s,k (s=0, 1, 2, 3) and stores the same in the storage section 54b. The shift-probability calculation unit 52 and backward-probability calculation unit 53 subsequently repeat the above calculations at k=kxe2x88x921, perform calculations from k=m2 to k=m1+1 and save the m2th backward probability xcex2m2(m) to the (m1+1)th backward probability xcex2m1+1(m) from k=m2 to k=m1+1 in the storage section 54b.  The shift-probability calculation unit 52 subsequently calculates the probabilities xcex33,k, xcex31,k, xcex32,k, xcex33,k using the receive data (yak,ybk) at time k (=m1+1). Further, the forward-probability calculation unit 53 assumes k=m1+1 and calculates the forward probabilities xcex11k(m), xcex10k(m) in each state m (=0 to 3) at time k using the forward probabilities xcex11kxe2x88x921(m), xcex10kxe2x88x921(m) at time (kxe2x88x921) and the obtained shift probabilities xcex30,k, xcex31,k, xcex32,k, xcex33,k at time k. The joint-probability calculation unit 56 and uk and uk likelihood calculation unit 57 perform operations similar to those described above and output uk and the likelihood L(uk). Thereafter, the shift-probability calculation unit 52, forward-probability calculation unit 55, joint-probability calculation unit 56 and the uk and uk likelihood calculation unit 57 repeat the foregoing calculations at k=k+1, perform the calculations from k=m1+1 to k=m2, calculate uk and the confidence (likelihood) L(uk) thereof at each time from k=m1+1 to m2 and output the same. Thereafter, (m2+1)th to Nth decoded data um2+1 to uN and likelihoods L(um2+1) to L(uN) are subsequently obtained in similar fashion. In accordance with the second aspect of the present invention, just rxc3x97m+(sxe2x88x921) (m: number of states) of memory capacity is needed to store backward probabilities in a case where m1=r, m2=2 r, m3=3 r . . . holds. Further, it is so arranged that backward probabilities are calculated in the reverse direction from an Nth backward probability to a first backward probability, the obtained backward probabilities are stored discretely and, if necessary, backward probabilities of the required number are calculated and utilized starting from one of the discretely stored backward probabilities. As a result, backward probability xcex2k(m) can be calculated accurately to make it possible to raise the precision of MAP decoding. (C) Turbo Decoder FIG. 9 is a block diagram illustrating a case where a MAP decoder according to the present invention is used as the element decoders DEC1, DEC2 in a turbo decoder (see FIG. 4). It is so arranged that the decoding operation in the element decoders DEC1, DEC2 is performed by a single MAP decoder. Components identical with those of the MAP decoder in FIG. 8 are designated by like reference characters. The MAP controller 50 controls the various timings of the MAP decoder in accordance with the operation sequence shown in FIG. 7. The input/output interleaver 51, which has RAMs 51a to 51c for storing receive data ya, yb, yc and a RAM controller 51d for controlling the reading and writing of receive data, outputs receive data in the order in which the data was input and, when appropriate, changes the output sequence to perform interleaving of the receive data. The shift-probability calculation unit 52, which calculates shift probability, has first and second arithmetic units 52a, 52b. The backward-probability calculation unit 53 calculates backward probabilities, as described in conjunction with FIGS. 7 and 8. The memory 54, which stores the backward probabilities, has the RAM 54a for discretely storing backward probabilities, the RAM 54b for storing backward probabilities continuously, and a RAM controller 54c for controlling the reading and writing of backward probabilities. The forward-probability calculation unit 55 calculates forward probabilities. The joint-probability calculation unit 56 multiplies the forward and backward probabilities together to calculate the probability that the kth item of data uk is xe2x80x9c1xe2x80x9d and the probability that it is xe2x80x9c0xe2x80x9d. The likelihood calculation unit 57 outputs the decoded results u and the a posteriori probability L(u). An S/P converter 61 subjects the receive data to a serial-to-parallel conversion and inputs the converted data to the input/output interleaver 51. The receive data ya, yb, yc obtained by the conversion is soft-decision data quantized at n bits. An external-information likelihood calculation unit 62 outputs external-information likelihood Le(u). In a first cycle of MAP decoding, the external-information likelihood calculation unit 62 outputs the external-information likelihood Le(u) using the a posteriori probability L(u) output from the likelihood calculation unit 57 and the MAP-decoder input signal (=signal ya). A write controller 63 writes the external-information likelihood Le(u) to a memory 64. A read-out controller 65 subjects the external-information likelihood Le(u) to interleaving and deinterleaving as appropriate by reading the external-information likelihood Le(u) out of the memory 64, and outputs the result as a posteriori likelihood L(uxe2x80x2) used in the next cycle of MAP decoding. In MAP decoding from the second cycle onward, turbo decoding is such that [signal ya+a posteriori likelihood L(uxe2x80x2)] is used as the input signal ya. Accordingly, in the second cycle of MAP decoding, the external-information likelihood calculation unit 62 outputs the external-information likelihood Le(u) using the a posteriori likelihood L(u) output from the likelihood calculation unit 57 and the decoder-input signal [=signal ya+a posteriori likelihood L(uxe2x80x2)]. The write controller 63 writes the external-information likelihood Le(u) to the memory 64. The read-out controller 65 subjects the external-information likelihood Le(u) to interleaving and deinterleaving as appropriate by reading the external-information likelihood Le(u) out of the memory 64, and outputs the result as a posteriori likelihood L(uxe2x80x2) used in the next cycle of MAP decoding. The external-information likelihood Le(u) is output in similar fashion thereafter. The following equation is established using the log value of each value: L(u)=Lya+L(uxe2x80x2)+Le(u)xe2x80x83xe2x80x83(8) The external-information likelihood calculation unit 62 therefore is capable of obtaining the external-information likelihood Le(u) in accordance with the following equation: Le(u)=L(u)xe2x88x92Lyaxe2x88x92L(uxe2x80x2)xe2x80x83xe2x80x83(9) where L(uxe2x80x2)=0 holds the first time. In a case where the write controller 63 finally outputs the decoded data u, the decoded data is written to the memory 64; otherwise, the write controller 63 writes the external-information likelihood Le(u) to the memory 64. In a case where the read-out controller 65 outputs the decoded data u, the read-out controller 65 reads the decoded data u out of the memory in the order in which the data was written. In a case where the read-out controller 65 reads out the external-information likelihood Le(u), the read-out controller 65 reads out and outputs (interleaves) the data in accordance with a read-out sequence specified by an interleave controller 66. A memory 67 has a RAM 67a and a RAM controller 67b and stores the interleaved external-information likelihood Le(u) as L(uxe2x80x2). FIG. 10 is a diagram useful in describing the sequence of turbo decoding. As is obvious from FIG. 4, turbo decoding is repeated a plurality of times treating a first half of decoding which uses ya, yb and a second half of decoding which uses ya, yc as one set. In the first half of decoding processing the first time, decoding is performed using receive signals Lcya, Lcyb and the likelihood L(u1) obtained is output. Next, the a posteriori probability Le(u1) is obtained in accordance with Equation (9) [where L(u1xe2x80x2)=0 holds], this is interleaved and L(u2xe2x80x2) is obtained. In the second half of decoding processing the first time, a signal obtained by interleaving the receive signal Lcya and the posteriori likelihood L(u2xe2x80x2) obtained in the first half of decoding processing are regarded as being a new receive signal Lcyaxe2x80x2, decoding is performed using Lcyaxe2x80x2 and Lcyc, and the likelihood (u2) obtained is output. Next, the a posteriori likelihood Le(u2) is found in accordance with Equation (9) and this is interleaved to obtain L(u3xe2x80x2). In the first half of decoding processing the second time, the receive signal Lcya and the a posteriori likelihood L(u3xe2x80x2) obtained in the second half of decoding processing are regarded as being a new receive signal Lcyaxe2x80x2, decoding is performed using Lcyaxe2x80x2 and Lcyb, and the likelihood (u3) obtained is output. Next, a posteriori likelihood Le(u3) is found in accordance with the above equation, this is interleaved and L(u4xe2x80x2) is obtained. In the second half of decoding processing the second time, a signal obtained by interleaving the receive signal Lcya and the posteriori likelihood L(u4xe2x80x2) obtained in the first half of decoding processing are regarded as being a new receive signal Lcyaxe2x80x2, decoding is performed using Lcyaxe2x80x2 and Lcyc, and the likelihood (u4) obtained is output. Next, the a posteriori likelihood Le(u4) is found in accordance with Equation (9) and this is interleaved to obtain L(u5xe2x80x2). The above-described decoding processing is subsequently repeated. Thus, in accordance with the first aspect of the present invention, a memory capacity of just rxc3x97m (m: number of states) is required to store the backward probabilities, where m1=r, m2=2 r, . . . holds. Moreover, since the backward probabilities are calculated from k=N at all times, backward probability xcex2k(m) is calculated accurately to make it possible to raise the precision of MAP decoding. Further, in accordance with a second aspect of the present invention, a memory capacity of just rxc3x97m+(sxe2x88x921) (m: number of states) is required to store the backward probabilities, where m1=r, m2=2 r, . . . holds. Further, in accordance with the second aspect of the present invention, it is so arranged that backward probabilities are calculated in the reverse direction from an Nth backward probability to a first backward probability, the obtained backward probabilities are stored discretely and, if necessary, backward probabilities of the required number are calculated and utilized starting from one of the discretely stored backward probabilities. As a result, backward probability xcex2k(m) can be calculated accurately to make it possible to raise the precision of MAP decoding. Moreover, in accordance with the second aspect of the present invention, backward probabilities of the required number need not be obtained by calculating backward probabilities from k=N on as the occasion demands. Operation speed can be raised as a result. Further, a prescribed operation speed is obtained without using two arithmetic circuits to calculate backward probability xcex2k(m). Furthermore, backward probability xcex2k(m) need be calculated just one time, thereby providing an advantage in terms of power consumption.