US 6,038,696 AGrant
Digital Transmission System and Method Comprising a Product Code Combined With a Multidimensional Modulation
Issue Date:2000-03-14
•7 Claims
•9 Drawing Sheets
Abstract
A digital transmission system wherein the transmitter applies a systematic convolutional code to the input data to generate a product code in blocks, with trellis closure by adding redundant data comprising a parity code bit. The thus coded data are then allocated to symbols that have undergone multidimensional digital modulation. At the receiver, iterative decoding is performed in cascade along two paths by computing hard decision reliabilities for each sub-set of the multidimensional digital modulation so as to produce soft decisions. The second path utilizes the results produced by the first path to form soft decisions. The soft decisions enable determination of output symbols. The invention also relates to a data protection method implemented in such a system.
Metadata
Assignee
- U.S. Philips Corporation
Inventors
- Antoine Chouly
- David Gianella
Application Information
Application Number:US 9876952
Filing Date:1997-12-09
Priority Date:1996-12-10
Art Unit:274
Classifications
IPC:
G06F 1110
Field of Search:
714375379754;757;759;792;795;790;786;789341;265;261;263;24438
Patent Drawings (9 sheets)
Description
Field of the Invention
The invention relates to a digital transmission system for protecting input data, comprising coding means for said data and iterative decoding means, the coding means comprising a first sub-set for performing a systematic convolutional trellis coding permitting of the iterative decoding, and a second sub-set for allocating the coded data to digitally modulated symbols.
The invention likewise relates to a method of protecting input data implemented in such a digital transmission system.
The system may be utilized for digital transmission for cable television, satellite television, terrestrial broadcasting, communication over telephone lines or otherwise.
Background of the Invention
Selective protection systems are known which combine convolutional coding with digital modulation. More particularly, for enhancing the performance of such a system in terms of bit error rates, a new class of convolutional codes called turbo codes has been described in the document entitled: "Near Shannon limit error-correcting coding and decoding: Turbo-codes (1), C. BERROU, A. GLAVIEUX, P. THITIMAJSHIMA, Proceeding of ICC '93, Geneva, May 1993, pp. 1064-1071. These turbo codes have a performance, expressed in bit error rates, close to theoretical limits provided by Shannon. They are parallel concatenated convolutional codes. These convolutional codes are based on systematic punctured recursive codes, that is, they are derived from codes of rate 1/2 with which one input bit gives rise to two output bits, the puncturing being applied to the bits themselves. The concatenation as such is realized by an appropriate interleaving of the data that contain the information.
At the receiver end, the iterative decoding, called turbo decoding, consists of decoding the received symbols several times to improve the performance of the system in terms of bit error rates. The successive iterative decodings are carried out by a single soft-decision Viterbi decoder. This decoder differs from a conventional Viterbi decoder which makes a hard decision. In this document, the soft decisions on the output of the decoder produce a hard-decision reliability ratio, that is, a correct decision likelihood. The decoder is then followed by a deinterleaving of the output data.
However the use of turbo codes followed by an iterative decoding, as disclosed in said documents does not suppress the limitations of punctured systematic codes with codes of rate 1/2, especially when the latter are applied separately from the digital modulation with which they co-operate. More particularly, a disadvantage of these codes is that they are adapted only to modulations having a low spectral efficiency (less than or equal to two bits/s/Hz), such as the MDP2 and MDP4 phase modulations. A bit rate equal to a maximum of twice the band used corresponds to these codes. For augmenting the rate for a fixed occupied band, one could look for utilizing high spectral efficiency modulations of the quadrature amplitude modulation type (QAM). But the use of the punctured convolutional codes described above, juxtaposed with QAM modulations, does not provide optimum performance, because these codes have been designed irrespective of the modulation.
Summary of the Invention
In it is an object of the invention to enhance the performance of such digital transmission systems while maintaining a proper functioning of the system with a minimum signal-to-noise ratio while improving their spectral efficiency.
This object is achieved with a digital transmission system in which the first sub-set utilizes a systematic convolutional trellis coding having a coding rate P/(Q.M), where M, P and Q are integers with Q and M being greater than 1, the systematic convolutional code being used for generating a product code in blocks with trellis closure by the addition of redundant data having at least one parity code bit. The product code is formed by components generated by row coding and column coding of a matrix that combines the coded data via the systematic convolutional code. The second sub-set combines the product code with a multidimensional amplitude modulation having dimension Q that has 2.sup.M states, the iterative decoding being a block decoding.
For generating the product code and the added redundant data on the basis of systematic convolutional codes, the coding means may comprise a so-called state machine which defines output states, redundancy symbols based on input states and data symbols.
Preferably, the state machine is coupled to a reading table for determining the redundancy symbols of the systematic convolutional code and the symbols used for closing the trellis.
According to the invention, the system is also characterized in that the iterative decoding means comprise at least two paths operating in succession:
along a first path, the system carried out a first iterative decoding with each iteration of the path with:
a) computing means for computing hard decisions which relate to the systematic convolutional code,
b) computing means for computing first reliabilities of the hard decisions associated with each multidimensional modulation sub-set, and second reliabilities associated to the trellis of the systematic convolutional code,
c) selecting means for selecting minimum reliabilities between the first and second reliabilities of each decision,
d) computing means for computing soft decisions used for the next iteration of the first path as a function of selected minimum reliabilities and hard decisions,
and along a second path, the system utilizes for each iteration of the path:
a) computing means for computing hard decisions which relate to the parity code,
b) computing means for computing third reliabilities for each hard decision of the second path as a function of hard decisions of the first path,
c) computing means for computing soft decisions as a function of the third reliabilities, soft decisions coming from the preceding iteration of the second path and hard decisions from the first path.
The invention also relates to an input data protection method utilized in a digital transmission system, the method comprising a coding phase for coding said data and an iterative decoding phase. The coding phase comprises a first systematic convolutional trellis code step which permits of iterative decoding, which step is combined with a second step of allocating coded data to digitally modulated symbols, characterized in that during the first step the systematic trellis coding has a coding rate P/(Q.M), where M, P and Q are integers with Q and M being greater than 1, the systematic convolutional code being used for generating a product code in blocks after trellis closure by the addition of redundant data. The product code is formed by components generated by row coding and column coding of a matrix that combines the coded data via the systematic convolutional code. The second step combines the product code with a multidimensional amplitude modulation dimension Q that has 2.sup.M states, the iterative decoding being a block of decoding.
A systematic convolutional coding is discussed here of rate P/(Q.M) preferably a rate 7/8. This coding is combined with a 2.sup.M -state (preferably 4-state) multidimensional digital modulation to provide optimum performance. According to this example (M=2, Q=8, P=14, rate=14/16=7/8), such a coding is obtained by processing a bit stream in which are taken 14 bits or 7 symbols (called input symbols) to be coded into eight symbols (called output symbols). The Q symbols (the eight output symbols, respectively) select two 2.sup.M -level symbols (four-level respectively {+1, -1, +3, -3}), that is to say, Q real symbols having the 2.sup.M -level amplitude modulation with M output bits per symbol (four-level 4-AM respectively, with two output bits per symbol). The product code is realized by applying the systematic convolutional code to the rows and columns of a matrix which contains the information bits with a trellis closure for each row and each column. Subsequently, the 2.sup.M -AM (for example, 4-AM) symbols coming from the matrix according to the product code are combined in pairs to generate 2.sup.2M -QAM symbols (for example, 16-QAM). The coded data are then transmitted by a carrier according to customary techniques.
For permitting the turbo decoding at the receiver end, the product code must be systematic. Therefore, systematic convolutional codes are to be used, that is to say, after coding the input data symbols occur on the output unchanged.
The convolutional codes of rate P/(Q.M), for example, 7/8, described hereinafter, are designed in such a way that they give the lowest error rate for a given signal-to-noise ratio and this specifically for the 4-AM or 16-QAM modulation.
In this manner, a system is obtained having optimum performance both as regards signal-to-noise ratio and spectral efficiency by the combination of a coder structure which realizes in optimum fashion the systemic convolutional coding with a rate 7/8 with the multidimensional modulation.
According to the invention, actually a product code using a systematic convolutional code is discussed here combined with a quadrature amplitude modulation and not a juxtaposition.
This system has various advantages.
Compared to the prior-art system, which utilizes binary punctured codes with an MDP4 phase modulation, one has a transmission capacity that is twice higher (spectral efficiency between two and four bits/s/Hz).
The system does not have much hardware complexity, because a single soft-decision decoder is necessary for performing the iterative decoding of the product code.
The codes used are preferably systematic convolutional codes of rate 7/8, with 14 input bits and 16 output bits. The function that generates the 16 output bits as a function of the input bits and of the state (memory) of the coder has been optimized in view of the 16-QAM modulation.
The systematic convolutional codes, preferably of rate 7/8 are chosen so that the minimum Euclidian distance of these codes combined with a 16-QAM modulation is maximized for improving the performance. This particularly refers to the combination of the coding and the modulation.
These and other aspects of the invention will be apparent from and elucidated with reference to the embodiments described hereinafter.
Brief Description of the Drawings
In the drawings:
FIG. 1: shows a diagram of a baseband digital transmission system according to the invention;
FIG. 2: shows a tree A.sub.0 partitioned into sub-sets;
FIG. 3: shows a general circuit diagram of a row or column coder permitting of generating the product code;
FIG. 4: shows a diagram of a digital transmission system comprising a coder for coding also the redundancy symbols;
FIG. 5: gives a representation of the partitioned tree of the 8-D constellation;
FIG. 6: gives a representation of the trellis of a code of rate 7/8;
FIG. 7: shows a general circuit diagram of a systematic convolutional coder of rate 7/8 combined with a 4-AM 8-D modulation;
FIG. 8: gives a representation of the bit allocation of the 4-AM symbols;
FIG. 9: represents a diagram showing a systematic convolutional coder for an 8-state code;
FIG. 10: represents a diagram showing a systematic convolutional coder for a 16-state code;
FIG. 11: shows a diagram of a particular embodiment of the coder represented in FIG. 7 for a code of rate 3/4;
FIG. 12 shows a diagram for the computation of the trellis closing symbols;
FIG. 13 shows a diagram of the decoding means of the first stage according to the invention;
FIG. 14: gives a representation of a trellis of the sub-sets S.sub.0.0 and S.sub.0.1 ;
FIG. 15 shows a flow chart of the various steps of the decoding carried out in the first stage;
FIG. 16: shows a diagram of the decoding means of the second stage according to the invention, and
FIG. 17: gives a representation in a trellis of the parity code.
Description of Embodiments
FIG. 1 represents a diagram of a baseband digital transmission system according to the invention. The input data to be protected coming from a source 5 are organized in a matrix, for example, by storing them in a memory 10 formed by rows and columns which may be addressed separately. The system comprises row coding means 12 and column coding means 14. The two coding means produce data which are allocated to 4-AM digitally modulated symbols. An allocation element 16 transforms the 4-AM symbols into 16-QAM symbols. This is a combination in pairs of the 4-AM symbols.
These symbols are transmitted according to customary techniques over a channel 19 to receiver means. The received data pass through buffer means 20 which permit of performing the loop processing to be described hereinafter. The decoder comprises two paths operating in succession, one path 1 which relates to the decisions about the least-significant bits of the transmitted symbols (index i), and a second path which relates to the decisions of the most-significant bits of the transmitted symbols (index j).
On path 1, on the output of the buffer means 20, the data enter a Viterbi decoder 22.sub.1 which has two outputs, a hard-decision output 21.sub.1 which delivers the estimated symbols and the estimated bits i obtained for each iteration, and a soft-decision output 23.sub.1 which is looped back to the buffer memory 20 through a data interleaver 24.sub.1.
On path 2, on the output of the buffer means 20, the data enter a parity code decoder 22.sub.2 which has two outputs, a hard-decision output 21.sub.2 which delivers the estimated bits j obtained for each iteration, and a soft-decision output 23.sub.2 which is looped back to the buffer 20 through a data interleaver 24.sub.2.
The decoding of the path 2 is performed after path 1 has been decoded, based on received symbols and bits i estimated by the decoder of the path 1.
The estimated symbols become more reliable as the iterative processing is repeated. On average, this improvement, measured in error rates, is obtained after 4 or 5 iterations for the path 1 and after 2 or 3 iterations for the path 2.
For forming the product code, the coding of a row of the matrix is carried out by the row coder in the following fashion. The data are processed in blocks, one block comprising 2.times.(7N+4).sup.2 bits for a systematic code of rate 7/8 taken here by way of example. The memory 10 stores an information matrix [I] of dimension (7N+4).times.(7N+4). The matrix contains quaternary data symbols {+1, -1, +3, -3}. Each symbol corresponds to 2 bits.
Then, each row of the matrix [I] (1 row=7N+4 symbols) is coded by a systematic convolutional row coder 122 (FIG. 3) generating both the data symbols (which are the 4-AM 4-level symbols {+1,-1,+3,-3} corresponding to the quaternary symbols of the matrix [I] before coding) and the redundancy symbols. For each row there are N 4-AM redundancy symbols generated by the convolutional 7/8 coder (N redundancy symbols for 7N data symbols) and 4 4-AM redundancy symbols for closing the code trellis. These 4 symbols are generated with the 4 last symbols of the row of the information matrix. The same operation is carried out for the columns of the matrix.
Consider by way of example the systematic convolutional code of rate 7/8 (coder 122). With 7 useful data symbols are generated 8 symbols comprising the 7 useful symbols (systematic convolutional code) plus one redundancy symbol. Consider the first row of the matrix formed by N+1 blocks (one block having 7 data symbols, that is, 14 bits) which are:
(I.sub.1,1, . . . I.sub.1,7), (I.sub.1,8, . . . I.sub.1,14), . . . , (I.sub.1,7N-6 . . . I.sub.1,7N), (I.sub.1,7N+1, . . . I.sub.1,7N+4).
A symbol, for example, I.sub.1,1, comprises two bits j.sub.1,1 and i.sub.1,1.
The product code realized according to the diagram of FIG. 3, gives a matrix represented in Table I.
For each block is computed the redundancy symbol (that is, 2bits) of the systematic convolutional code, block 1 produces R.sub.1,1, block 2 produces R.sub.1,2 and so on and so forth up to block N which produces R.sub.1,N.
There is supposed that the initial state of the coder is equal to zero. After generating R.sub.1,N, the coder 122 is in state .sigma.(N). With the aide of the trellis closing means 128, the trellis is closed by forcing the state of the trellis to zero by generating 4 symbols TR.sub.1,1, TR.sub.1,2, TR.sub.1,3, TR.sub.1,4 (for an 8-state code) corresponding to a transition in the trellis of the 8-state convolutional code, so that after this transition one arrives at the state .sigma.=0. For a code having more states, it is necessary to use more trellis closing symbols. The symbols TR.sub.1,1, TR.sub.1,2, TR.sub.1,3, TR.sub.1,4 are functions of the 4 data symbols (I.sub.1,7N+1, . . . I.sub.1,7N+4) and of the state of the trellis .sigma.(N) after a row has been coded and are generated by a Table addressed by .sigma.(N) described hereinafter.
After the coding, the matrix of 4-AM symbols represented in Table I is obtained in which:
I.sub.m,n is a matrix having dimensions (7N+4).times.(7N+4) comprising the 4-AM data symbols.
R.sub.m,n is a matrix having dimensions (7 N+4).times.N comprising the 4-AM symbols that correspond to the row redundancy symbols generated by the 7/8 code.
TR.sub.m,n is a matrix having dimensions (7N+4).times.4 comprising the 4-AM trellis closing row redundancy symbols.
C.sub.m,n is a matrix having dimensions (N.times.7N+4) comprising the column redundancy symbols.
TC.sub.m,n is a matrix having dimensions (4.times.7N+4) comprising the trellis closing column redundancy symbols.
The row coder 12 operates in the following manner (FIG. 3). The input symbols I.sub.m,n enter the buffer 120 and then the coder 122 of rate 7/8 which produces one redundancy symbol for a block of 7 data symbols. A multiplexer 124 serializes the symbols on the output. Therefore, it supplies on its output 131, in sequence, groups of 8 symbols while each group is formed by the 7 data symbols and the redundancy symbol corresponding to this block. The multiplexer then supplies all the groups of 8 symbols in succession. When all the groups have been extracted, the 4 last data symbols of the row are extracted and then the 4 trellis closing symbols produced by the element 128 for determining closing symbols. A controller 17 controls the operations.
The same process is carried out for the other rows. In like manner, a similar process is realized for the columns (column coder 14). The first block of the first column is formed by the symbols: I.sub.1,1,I.sub.2,1 . . . I.sub.7N+4,1. One redundancy symbol corresponds to each block of 7 symbols, for example, the symbol C.sub.1,1 corresponds to the first block and the symbol C.sub.N,1 corresponds to the last block. The trellis closing redundancy symbols for the first column are the symbols TC.sub.1,1, TC.sub.2,1, TC.sub.3,1, TC.sub.4,1 generated on the basis of the symbols I.sub.7N+1,1, . . . I.sub.7N+4,1. All the data formed by the initial-data symbols, the row coding redundancy symbols and the column coding redundancy symbols and the trellis closing symbols form the product code.
One row of this product code forms a block of symbols which is used for coding 4-AM modulation symbols. As the initial-data symbols remain the same in the product code whether they are read in rows or in columns, for utilizing the columns of the product code it is needless to use the initial-data symbols once again. Thus only the redundancy symbols of the columns of the product code are used for coding (column coder 14) 4-AM modulation symbols. The 4-AM symbols coming from the rows and columns of the product code are used for coding a 16-QAM modulation in the allocation element 16.
For enhancing the performance of the system it is possible to code also the redundancy symbols which have just been computed.
In this manner, the columns of the matrices R.sub.m,n and TR.sub.m,n (row redundancy column coding) may be coder for generating the matrices RC.sub.m,n, TRC.sub.m,n, RCT.sub.m,n and TRCT.sub.m,n having dimensions (N.times.N), (N.times.4), (4.times.N) and (4.times.4), respectively (Table II). Also coded in rows is the column redundancy (matrices C.sub.m,n and TC.sub.m,n) for generating the matrices CR.sub.m,n, CRT.sub.m,n, TCR.sub.m,n and TCRT.sub.m,n having dimensions (N.times.N), (N.times.4), (4.times.N) and (4.times.4), respectively.
In this case, the information matrix having dimensions (7N+4).times.(7N+4) following the rows and columns for obtaining the row redundancy (symbols R.sub.m,n and TR.sub.m,n) and the column redundancy (symbols C.sub.m,n and TC.sub.m,n) in the same manner as that which has just been described. Then the row redundancy is coded in a column and the column redundancy is coded in a row in order to enhance the performance of the system. Thus, for example, the block of 7N+4 symbols (R.sub.1,1, . . . , R.sub.7N+4,1) is coded to generate first the N column redundancy symbols (RC.sub.1,1, . . . , RC.sub.N,1) coming from the 7/8 code redundancy and then the four redundancy symbols (RCT.sub.1,1 to RCT.sub.4,1) for closing the trellis. The same is carried out for the other columns of the row redundancy (R.sub.1,n, . . . , T.sub.7N+4,n) for n=1, . . . , N for the redundancy are coded, that is, the rows (C.sub.m,1, . . . ,C.sub.m,7N+4) for m=1, . . . ,N and the 4 rows (TC.sub.1,1, . . . , TC.sub.1,7N+4) up to (TC.sub.4,1, . . . , TC.sub.4,7N+4).
Thus the following matrix is obtained:
In this Table:
the matrix [I] contains the input data symbols,
the matrix [R] is the row redundancy matrix of the matrix [I],
the matrix [C] is the column redundancy matrix of the matrix [I],
the matrix [TR] is the trellis closing redundancy matrix for the rows of the matrix [I],
the matrix [TC] is the trellis closing redundancy matrix for the columns of the matrix [I],
the matrix [RC] is the column redundancy matrix of the matrix [R],
the matrix [CR] is the row redundancy matrix of the matrix [C],
the matrix [TCR] is the row redundancy matrix of the matrix [TC],
the matrix [RCT] is the trellis closing redundancy matrix for the columns of the matrix [R],
the matrix [TRC] is the column redundancy matrix of the matrix [TR],
the matrix [TRCT] is the trellis closure matrix for the columns of the matrix [TR],
the matrix [CRT] is the trellis closure matrix of the rows of the matrix [C],
the matrix [TCRT] is the trellis closure matrix of the row coding of the matrix [TC].
Consider in more detail the operation of the row coder 12 represented in FIG. 3 for coding a row of the matrix.
In the buffer 120 is stored the row one wishes to code. One row comprises (14N+8) bits or (7N+4) quaternary data symbols. For example, for the block of the k.sup.th order, the buffer stores N blocks (i.sub.1 (k), j.sub.1 (k), . . . , i.sub.7 (k), j.sub.7 (k)) having 14 bits (that is, 7 symbols) and 1 block of 8 bits (that is 4 symbols):
i.sub.1 (N+1),i.sub.1 (N+1)
i.sub.2 (N+1),i.sub.2 (N+1)
i.sub.3 (N+1),i.sub.3 (N+1)
i.sub.5 (N+1),i.sub.5 (N+1)
The N blocks of 14 bits are successively subjected to a systematic convolutional coding of rate 7/8 (coder 122). For each block (k.sup.th block), the coder 122 generates 7 4-AM data symbols U.sub.1 (k) to U.sub.7 (k) which corresponds to 14 information bits of the block and 1 redundancy symbol U.sub.8 (k), for k=1, . . . ,N, (connection 123) by realizing a bit allocation described in FIG. 8.
Each block of 14 information bits corresponds to a transition in the 7/8-code trellis. The last block of the N+1.sup.th order corresponds to the transition that closes the trellis.
Based on the 8 information bits {i.sub.1 (N+1), j.sub.1 (N+1), i.sub.2 (N+1), j.sub.2 (N+1), i.sub.3 (N+1), j.sub.3 (N+1), i.sub.5 (N+1), j.sub.5 (N+1)}, (4 quaternary symbols) which are the 8 last bits of the row, the 4-AM symbols are generated, that is, U.sub.1 (N+1), U.sub.2 (N+1), U.sub.3 (N+1), U.sub.5 (N+1) just like the bit allocation given by FIG. 8, after which the 4 redundancy symbols U.sub.4 (N+1), U.sub.6 (N+1), U.sub.7 (N+1) and U.sub.8 (N+1) are computed, permitting of closing the trellis. These symbols are both a function of the state of the coder .sigma..sub.N+1 after the coding of the N.sup.th block and of the 8 bits {i.sub.1 (N+1), j.sub.1 (N+1), i.sub.2 (N+1), j.sub.2 (N+1), i.sub.3 (N+1), j.sub.3 (N+1), i.sub.5 (N+1), j.sub.5 (N+1)}. They are determined by element 128.
The column coder is the same except on the output of the systematic convolutional 7/8 coding where they are only the redundancy symbols.
The diagram of the coder which permits to make the double coding of the redundancy is represented in FIG. 4. Like elements to those of FIG. 1 are represented having like references. In the case of the example under consideration, the memory M 10 contains (7N+4).sup.2 symbols. Another memory MR contains the (7N+4)(N+4) row redundancy symbols (symbols R.sub.m,n, TR.sub.m,n). Another memory MC contains the (N+4)(7N+4) column redundancy symbols (symbols C.sub.m,n and TC.sub.m,n). The memories MR and MC are loaded after finishing the row and column coding of M. Then, the coding of the contents of MR is performed following the columns and the coding of the contents of MC following the rows for generating the (N+4).sup.2 4-AM symbols (RC.sub.m,n, TRC.sub.m,n, RCT.sub.m,n and TRCT.sub.m,n) and the (N+4).sup.2 4-AM symbols (CR.sub.m,n, CRT.sub.m,n, TCR.sub.m,n, and TCRT.sub.m,n), respectively. Switches 13 and 15 ensure the running of the operations under the control of the controller 17.
Finally, all the 4-AM symbols formed for each product code matrix of the Tables I or II are combined to pairs and transmitted over the channel in the form of complex symbols of the 16-QAM constellation (in a well-defined order).
The rate of the product code without redundancy coding is equal to: ##EQU1## For N=20, the rate is 0.765 and the spectral efficiency is thus equal to 4 times this rate, that is, 3.06 bits/s/Hz.
With a double redundancy coding, the rate of the product code becomes equal to: ##EQU2##
Thus, with N=20, a rate 0.72 is obtained and a spectral efficiency of 2.88 bits/s/Hz. There is a loss of spectral efficiency when coding the redundancy of 0.18 bits/s/Hz, but the performance of the system is enhanced.
FIG. 8 represents the bit allocation of the bits i,j to the symbols of the 4-AM constellation.
The 4-AM constellation having a 1-D dimension is represented by the set A.sub.0 ={-3,-1,+1,+3}. The first partition level of A.sub.0 comprises two sub-sets B.sub.0 and B.sub.1 with B.sub.0 ={3,-1} and B.sub.1 ={1,-3} (FIG. 2). A symbol, for example I.sub.1,1 comprises two bits i.sub.1,1 and j.sub.1,1. The bit i is allocated to this first level with i=0 for B.sub.0 and i=1 for B.sub.1.
The second partition level of A.sub.0 comprises four sub-sets C.sub.0, C.sub.1, C.sub.2 and C.sub.3, with C.sub.0 ={+3}, C.sub.1 ={+1}, C.sub.2 ={-1} and C.sub.3 ={-3}. The index j is allocated to this second level, with j=0 for C.sub.0 or C.sub.1 and j=1 for C.sub.2 or C.sub.3. The index of the sets C is equal to the decimal value of the indices j,i, that is, 2j+i, allocated to the partition generating them.
An 8-D constellation is defined as being the set of the blocks of 8 symbols belonging each to A.sub.0. FIG. 5 represents the partition tree of the 8-D constellation (A.sub.0).sup.8 where A.sub.0 is the one-dimension (1-D) 4-AM constellation.
The set (A.sub.0).sup.8 has do.sup.2 for the (squared) minimum Euclidian distance. This set is divided into 2 sub-sets having a minimum distance of 2do.sup.2. To each sub-set is allocated a bit Y.sub.0 having the 0 or 1 value.
Y.sub.0 =0 for the sub-set formed by all the blocks belonging to B.sub.i1, . . . ,B.sub.i8 with ##EQU3##
Y.sub.0 =1 for the sub-set formed by all the blocks belonging to B.sub.i1. . . B.sub.i8 with ##EQU4##
Thus, Y.sub.0 =0 corresponds to the set of all the 4-AM symbol blocks (U.sub.1 . . . U.sub.8) containing an odd number of components in the 1-D sub-set, that is B.sub.1 ={+1, -3}.
Similarly, Y.sub.0 =1 corresponds to the set of all the 4-AM symbol blocks (U.sub.1 . . . U.sub.8) containing an odd number of components in the 1-D sub-set, that is B.sub.1 ={-1, +3}.
Then, each 8-D sub-set is in its turn divided into 2 other 8-D sub-sets, and so on and so forth.
To each partition level is allocated one bit:
Y.sub.0 is allocated to the first level;
Y.sub.1 is allocated to the second level;
Y.sub.2 is allocated to the third level;
Y.sub.3 is allocated to the fourth level;
In the following will be described only the sub-sets corresponding to Y.sub.0 =0.
After the 4.sup.th partition level, the 8 sub-sets:
S.sub.0, S.sub.2, S.sub.4, S.sub.6, S.sub.8, S.sub.10, S.sub.12, S.sub.14 (S.sub.i, i even) are obtained.
The index i of a sub-set S.sub.i is the decimal value of 4 bits Y.sub.3, Y.sub.2, Y.sub.1, Y.sub.0, allocated to S.sub.i.
Each sub-set has the form U(B.sub.i1 . . . B.sub.i8) (union of the sub-sets) and is defined by parity relations of the indices (i.sub.1, . . . i.sub.8). The minimum (squared) distance in each sub-set S.sub.i is 4-do.sup.2. Each sub-set contains 2.sup.12 =4096 blocks of 8 4-AM symbols.
Each sub-set S.sub.i contains 16 sub-sets (B.sub.i1 . . . B.sub.i8) and each sub-set (B.sub.i1 . . . B.sub.i8) contains 2.sup.8 =256 8-D blocks.
Finally, each sub-set S.sub.i is divided into 2 sub-sets S.sub.i,0 and S.sub.i,1, where:
S.sub.i,0 is the sub-set of the blocks of S.sub.i of which the last 4-AM symbol of the block is positive (thus belonging to C.sub.0 or C.sub.1).
S.sub.i,1 is the sub-set of the blocks S.sub.i of which the last 4-AM symbol of the block is negative (thus belonging to C.sub.2 or C.sub.3).
Thus, S.sub.i,0 corresponds to the set of the 8-D blocks of S.sub.i of which the last symbol U.sub.8 is in C.sub.0 or C.sub.1, that is to say, that the last symbol corresponds to the bit j.sub.8 =0. S.sub.i,0 contains 2.sup.11 elements.
S.sub.i,1 ={(U.sub.1, . . . U.sub.8) of S.sub.i, so that j.sub.8 =1}.
For example, the sub-set S.sub.6,1 is defined by the set of the blocks (U.sub.1, U.sub.2, . . . U.sub.8) of (A.sub.0).sup.8 verifying j.sub.8 =1 and the 4 parity relations of the bits i.sub.1 to i.sub.8 : ##EQU5## where (i.sub.p, j.sub.p) are the bits allocated to the 4-AM symbol U.sub.p (FIG. 8).
In the general case, for even i, S.sub.i,j is the set of the blocks U=(U.sub.1, . . . ,U.sub.8) of 4-AM symbols verifying the following parity relations ##EQU6## where (Y.sub.3 Y.sub.2 Y.sub.1 Y.sub.0) is the bit representation of i, that is to say:
i=8Y.sub.3 +4Y.sub.2 +2Y.sub.1 +Y.sub.0, with Y.sub.0 =0 and (i.sub.p, j.sub.p) is the bit allocation of the p.sup.th symbol of the block U.sub.p : ##EQU7##
Thus, for generating all the S.sub.i,j blocks (2.sup.11 blocks), it is sufficient to scan all the possible combinations of the 11 bits i.sub.1, i.sub.2, i.sub.3, i.sub.5, j.sub.1, j.sub.2, j.sub.3, j.sub.4, j.sub.5, j.sub.6 and j.sub.7. For a given combination, the other bits (i.sub.4, i.sub.6, i.sub.7, i.sub.8, j.sub.8) are computed based on the parity relations of the sub-set S.sub.i,j defined above.
The systematic 7/8-rate convolution code is formed in the following manner:
The sub-sets S.sub.i,j are allocated to the parallel branches of the trellis. Moreover, the sub-sets S.sub.i,j with even i are utilized. This ensures a minimum distance (squared) equal to 4do.sup.2 where do is the minimum distance of the 4-AM constellation.
For having a code with a rate 7/8, there must be 8 separate transitions coming from a given state of the coder, which corresponds to 14 input bits (of which 3 coded bits and 11 non-coded bits) for 8 transmitted 4-AM symbols (that is, 16 bits). Consequently, the trellis of an 8-state code is connected completely.
For having a systematic code, that is, for providing that the transmitted 7 first 4-AM symbols of the 8-D block are the 7 data symbols (or 14 bits), it is necessary for the 2.sup.14 transitions based on a state to generate 2.sup.14 blocks of 8 4-AM symbols, the 7 first ones employing the 2.sup.14 possible combinations. Therefore, it is sufficient to allocate 8 sub-sets S.sub.i,j, where i=0, 2, 4, 6, 8, 10, 12, 14 and j is an arbitrary value, to the 8 separate branches coming from one state.
FIG. 6 shows the trellis of the optimum 7/8 systematic convolutional code. In this Figure, .sigma..sub.k is the state of the coder at the instant k and .sigma..sub.k+1 is the state of the coder at the instant k+1, the state being defined by the 3 bits in the memory of the coder (3 shift registers). This Figure also shows the allocation of the sub-sets S.sub.i,j to the various trellis transitions. The trellis is analyzed in the following manner:
Based on the state .sigma.(k) at the instant kt:
.sigma..sub.k =(.sigma..sub.k.sup.2,.sigma..sub.k.sup.1,.sigma..sub.k.sup.0), the coder proceeds to another state .sigma.(k+1) at an instant (k+1)T: .sigma..sub.k+1 =(.sigma..sub.k+1.sup.2,.sigma..sub.k+1.sup.1,.sigma..sub.k+1.sup.0).
Thus from the state [111] the coder can go over to one of the 8 states [000][001][010][011][100][101][110][111].
For example, it is observed that the third transition coming from the state 001, that is to say, the transition 001.fwdarw.010, corresponds to S.sub.10,1. The whole trellis is analyzed in like manner.
FIG. 7 shows the block diagram of the coder 122 of rate 7/8 (FIG. 3). The 14 bits on the input of the coder at the instant k, (i.sub.1 (k), j.sub.1 (k) l=1 . . . 7, select the 7 first symbols of the transmitted block U.sub.1 (k), . . . U.sub.7 (k) as shown in FIG. 8. For computing the redundancy symbol U.sub.8 (k), that is, (i.sub.8 (k), j.sub.8 (k)), first the index i (even i) of the sub-set S.sub.i is computed which corresponds in like manner to the 3 bits Y.sub.3 (k), Y.sub.2 (k), Y.sub.1 (k) with i=8Y.sub.3 +4Y.sub.2 +2Y.sub.1 +Y.sub.0, Y.sub.0 =0. Also i.sub.8 (k) is computed, which is the parity bit of the bits i.sub.1 (k), . . . i.sub.7 (k). The bit j.sub.8 (k) is the redundancy bit of a systematic convolutional coder 230 of rate 3/4 having for its inputs the bits Y.sub.1, Y.sub.2, and Y.sub.3. The bits (i.sub.8, j.sub.8) select the symbol U.sub.8 (k). On the 3/4 code output one has the next state of the coder .sigma..sub.k+1 which will be used for closing the trellis at the end of a row or of a column (k=N).
The computation of the bits Y.sub.1 (k), Y.sub.2 (k), Y.sub.3 (k) and i.sub.8 (k) as a function of the bits i.sub.1 (k), i.sub.2 (k), . . . i.sub.7 (k) is given by the following equations:
These equations are derived from the bit allocation of the sub-sets S.sub.i to the bits Y.sub.0, Y.sub.1, Y.sub.2, and Y.sub.3 (FIG. 5) which is realized in element 210.
This structure of the coder (FIG. 7) permits of allocating all the 8-D blocks of S.sub.i,j8 with i=8Y.sub.3 +4Y.sub.2 +2Y.sub.1 to the parallel transitions of the trellis from a state .sigma. to another state.
The convolutional coder of FIG. 7 may be realized either via a Table (FIG. 11), or by shift registers (FIGS. 9 and 10), or by software of a computer.
In FIG. 11, the Table 220 (memory) gives the redundancy bit j.sub.8 (k) and the future state .sigma..sub.k+1 (.nu. bits for a code having 2.sup..nu. states), as a function of .sigma..sub.k, Y.sub.1 (k), Y.sub.2 (k), Y.sub.3 (k). The Table 220 receives Y.sub.1, Y.sub.2, Y.sub.3 and also its output .sigma..sub.k+1 which is looped back to the input through a delay cell 222.
FIGS. 9 and 10 show the diagrams of the optimum, 8-state codes (.nu.=3) and 16-state codes (.nu.=4). For an 8-state code, a chain is formed by an adder cell 312.sub.1, a delay cell 310.sub.1, an adder cell 312.sub.2, a delay cell 310.sub.2, an adder cell 312.sub.3, a delay cell 310.sub.3, an adder cell 312.sub.4, while the output of the system produces j.sub.8 (k).
The adder cell 312.sub.1 receives Y.sub.1 (k),
The adder cell 312.sub.2 receives Y.sub.3 (k),
The adder cell 312.sub.3 receives Y.sub.2 (k) and Y.sub.3 (k),
The adder cell 312.sub.4 receives Y.sub.1 (k), Y.sub.2 (k) and Y.sub.3 (k).
For a 16-state code (FIG. 10), a system is formed by the same elements as for the 8-state system with additionally a delay cell 310.sub.4 and an adder cell 312.sub.5.
FIG. 12 relates to the trellis closure arrangement. Let us consider the state .sigma. of the coder and the sub-sets S.sub.i,j8 (8-D sub-sets) allocated to the transition (2.sup.11 parallel branches) closing the trellis.
As there are 2.sup.11 branches at which the trellis can be closed, one will look for the branch as a function of the 4 data symbols U.sub.1, U.sub.2, U.sub.3 and U.sub.5, that is, 8 information bits i.sub.1, j.sub.1, i.sub.2, j.sub.2, i.sub.3, j.sub.3, i.sub.5 and .sub.5.
During the closing transition of the trellis, 4 data symbols U.sub.1, U.sub.2, U.sub.3 and U.sub.5 are transmitted corresponding to the bits (i.sub.1,j.sub.1), (i.sub.2,j.sub.2), (i.sub.3,j.sub.3) and (i.sub.5,j.sub.5), respectively.
The computation is made in two steps (FIG. 12): Based on the state .sigma..sub.N+1 of the coder at the end of the coding of a row or of a column, the bits Y.sub.1 (N+1), Y.sub.2 (N+1), Y.sub.3 (N+1) and j.sub.8 (N+1) are generated on the basis of the Table 210 which contains the Table III.
Based on the bits Y.sub.1 (N+1), Y.sub.2 (N+1), Y.sub.3 (N+1) and j.sub.8 (N+1), the bits (i.sub.4, j.sub.4), (i.sub.6, j.sub.6), (i.sub.7, j.sub.7) and (i.sub.8, j.sub.8)(N+1) are computed making it possible to generate the symbols U.sub.4 (N+1), U.sub.6 (N+1), U.sub.7 (N+1) and U.sub.8 (N+1) in computing means 240. These bits are computed via:
The bits j.sub.4 and j.sub.6 may assume whatever value. They are determined to be, for example, 0 (j.sub.4 =j.sub.6 =0).
The bit j.sub.7 is the parity bit of all the bits (j.sub.1, . . . j.sub.7) of the preceding transitions: ##EQU8## This is effected in the computing means represented in FIG. 12. Preferably, the computations are realized via software of a computer.
The decoding means are shown in FIG. 1. The decoding is carried out in steps in two different stages. In the first stage an iterative decoding is carried out of the least-significant bits (LSB) of the transmitted symbols (bits i).
The matrix of the symbols received through the channel is stored in a memory 20, which matrix corresponds to the matrix of the transmitted symbols (the dimension of the matrix is the same as that of the matrix coded at the transmitter end).
The rows and after that the columns are successively decoded independently. With each iteration, the decision (connection 21.sub.1) on the bits i (bit matrix) is generated and a real-symbol matrix (reliability of the decision) which will be used during the next iteration is stored in the memory 20 (connection 23.sub.1). A de-interleaver 24.sub.1 delays the data.
For the decoding of a row and of a column, a soft-decision Viterbi decoder 22.sub.1 is used corresponding to the 8-D 7/8 convolutional code for the desired example.
In the second stage, after a certain number of iterations for the first step (generally 3 or 4), one proceeds to step 2 (connection 25) for decoding the bits j, that is to say, the most-significant bits (MSB) of the transmitted symbols.
Rows and after that columns are then iteratively decoded in that the real-symbol matrix stored in memory 20 and the matrix of the bits i detected in the first stage are used.
The decoder 22.sub.2 of a row or of a column is a soft-decision decoder of the parity code used when the trellis of the 7/8 convolutional code is closed for each row and column of the product code.
First, consider the operation of the first stage (path 1). FIG. 13 represents the general circuit diagram of a stage comprising the means that double-decision Viterbi decoding means 22.sub.1 for the LSB bits of the transmitted 4-AM symbols (bits i). They comprise:
a sub-set 220 for computing matrices,
a Viterbi decoder 222 which produces hard decisions,
a sub-set 224 for computing the reliability of the decisions,
a sub-set 226 for computing soft decisions.
The decoding of systematic convolutional codes consists of applying a soft-decision decoding algorithm. For simplicity of the exposition, the systematic convolutional code of rate 7/8 will be taken as an example. According to the particular example described for the row having index 1 in the Table I, a range of the product code is formed by the following symbols which have been transmitted at the transmitter end (for simplicity of the exposition, the row index, here i=1, is omitted in the following):
7N+4 data symbols:
I=I.sub.1, . . . ,I.sub.7N+4
N code redundancy symbols:
R=R.sub.1, . . . ,R.sub.N
4 trellis closing symbols:
TR=TR.sub.1,TR.sub.2,TR.sub.3,TR.sub.4.
Because of the imperfections of the transmit channel, the received symbols D.sup.(0) =(D.sub.1.sup.(0), . . . ,D.sub.8N+8.sup.(0)) will present differences compared with the transmitted symbols.
At the receiver end, complex symbols are received which correspond to the transmitted 16-QAM symbols after passing through the channel. Each complex symbol is considered to be the sequence of 2 real symbols. Then, these real symbols are stored in the memory 20 (FIG. 1) in accordance with the matrix which has the same structure as the matrix defined at the transmitter end. The received real symbols are arranged in the matrix while adhering to the same order as that used at the transmitter end. The decoding process of the bits i is iterative, which means that the rows of the matrix are decoded first and then the columns. The number of rows or columns to be decoded with each iteration is equal to 7N+4 in the case of Table I (without redundancy coding) or equal to 8N+8 in the case where the redundancy is coded (Table II).
First, let us consider the iterative decoding at the v.sup.th iteration for a row of the matrix, that is to say, a block of real symbols: D.sup.(.nu.-1) =(D.sub.1.sup.(.nu.-1), . . . ,D.sub.8N+8.sup.(.nu.-1)). The index v is an integer corresponding to the number of the iteration. The decoding produces the block: D.sup.(.nu.) =(D.sub.1.sup.(.nu.), . . . ,D.sub.8N+8.sup.(.nu.)) of 8N+8 real symbols (soft output) which will be applied to the next iteration and to the optimum decision of the bits i.sup.(.nu.) =(i.sub.1.sup.(.nu.), . . . ,i.sub.8N+8.sup.(.nu.)) corresponding to the transmitted bits i=(i.sub.1, . . . ,i.sub.8N+8) which are the bits of the first partition level (LSB bits) of the transmitted 4-AM symbols (I.sub.1, . . . I.sub.7N+4,R.sub.1, . . . R.sub.N,TR.sub.1, . . . TR.sub.4), respectively. It is supposed that the 7N+4 symbols D.sub.1.sup.(.nu.-1), . . . ,D.sub.7N+4.sup.(.nu.-1) correspond to the data symbols, and the N symbols D.sub.7N+5.sup.(.nu.-1), . . . ,D.sub.8N+4.sup.(.nu.-1) correspond to the 7/8 code redundancy symbols and the 4 symbols D.sub.8N+5.sup.(.nu.-1), . . . ,D.sub.8N+8.sup.(.nu.-1) are the redundancy symbols for closing the trellis. The symbols are processed in the following order: ##EQU9##
The decoding is performed in six steps. The following exposition indicates the manner in which D.sup.(.nu.) is derived from D.sup.(.nu.-1).
The first step relates to the computation of the metrics. The sub-set 220 for computing the metrics (FIG. 13) carries out for each block of 8 symbols (1.sup.st block, l=0, . . .N-1) (D.sub.7l+1.sup.(.nu.-1), - - - D.sub.7l+7.sup.(.nu.-1), D.sub.7N+5+l.sup.(.nu.-1)) the detection and the computation of metrics in each 8-D sub-set S.sub.i,j, and for the block (D.sub.7N+1.sup.(.nu.-1), - - - D.sub.7N+4.sup.(.nu.-1),D.sub.8N+5.sup.(.nu.-1), . . . D.sub.8N+8.sup.(.nu.-1)) corresponding to the transition that closes the trellis at the end of the coding of a row or of a column of the product code. For simplicity, the 8-D block is denoted (r.sub.1, - - - r.sub.8). The computation of the metrics is carried out in various steps.
First consider the computation of the metrics in the 1-D constellation. For k=1, . . . 7 (the first 7 symbols of the block), the nearest 4-AM symbol is detected in each of the sub-sets B.sub.0 ={3, -1} and B.sub.1 ={1,-3} and the corresponding metric is computed: M.sub.k,0 and M.sub.k,1, respectively, where M.sub.k,i is equal to the squared Euclidian distance between r.sub.k and the nearest symbol in B.sub.i.
For k=8, the metrics M.sub.8,0, M.sub.8,1, M.sub.8,2 and M.sub.8,3 of the symbol r.sub.8 in each sub-set C.sub.i are computed, with Ci=0, 1, 2, 3, respectively, where C.sub.i contains the 4-AM point corresponding to the value i in decimal form of the 2 bits allocated to the 4-AM constellation.
Thereafter, the metrics are computed in the 2-D constellation. For the 3 first 2-D blocks (symbol pairs), that is, (r.sub.1, r.sub.2) (r.sub.3, r.sub.4) and (r.sub.5, r.sub.6), the metrics M.sub.k,l.sup.(2) for k=1, 3, 5 are detected and computed in the 4 2-D sub-sets E.sub.l.sup.(2) =B.sub.i B.sub.i' with l=2i+i', i=0, 1 and i'=0, 1.
The 2-D metric is defined as being the sum of the 2 1-D metrics of the 2 symbols of 2-D block. The metric of (r.sub.k, r.sub.k+1) in E.sub.l.sup.(2) is obtained for k=1, 3, 5:
for l=0, 1, 2, 3
with l=2i+i'.
For the last 2-D block r.sub.7, r.sub.8, the metrics M.sub.7,l,j.sup.(2) are computed in the 8 2-D sub-sets E.sub.lj.sup.(2) =B.sub.i C.sub.2j+i' for i=0, 1, i'=0, 1, j=0, 1 with l=2i+i':
Thereafter, the metrics are computed in the 4-D constellation. The metrics M.sub.1,l.sup.(4) are detected and computed of the 4-D block (r.sub.1 r.sub.2 r.sub.3 r.sub.4) in the 8 four-dimension sub-sets E.sub.l.sup.(4), with l=0, 1, . . . 7:
For each sub-set 2 4-D metrics are computed and the smaller metric is taken. For example, for E.sub.0.sup.(4) is computed:
the metric M.sub.1,3.sup.(2) +M.sub.3,3.sup.(2) in E.sub.3.sup.(2) E.sub.3.sup.(2) ;
the metric M.sub.1,3.sup.(2) +M.sub.3,3.sup.(2) in E.sub.3.sup.(2) E.sub.3.sup.(2) ;
the metric M.sub.1,0.sup.(4) in E.sub.0.sup.(4) of (r.sub.1 r.sub.2 r.sub.3 R.sub.4), equal to:
For the block (r.sub.5 r.sub.6 r.sub.7 r.sub.8), the metrics M.sub.5,l,j.sup.(4) in the sub-sets E.sub.l,j.sup.(4) for l=0,1, . . . 7 and j=0,1 are detected and computed. The sub-sets E.sub.l,j.sup.(4) are defined in similar fashion to E.sub.l.sup.(4) except that the last symbol is positive for j=0 and is negative for j=1. For example, E.sub.0,j.sup.(4) =E.sub.0.sup.(2) E.sub.0,j.sup.(2) U E.sub.3.sup.(2) E.sub.3,j.sup.(2). Thus it is sufficient to replace the index k of the second 2-D sub-set by k,j. The metric in E.sub.0,j.sup.(4) is:
Finally, the metrics are computed in the 16 8-D sub-sets. The sub-set S.sub.i,j for even i is the union of the 4 8-D sub-sets, each being the concatenation of 2 4-D sub-sets:
S.sub.i,j =U E.sub.l.sup.(4) E.sub.l'j.sup.(4) with i.sub.2 =0,1 and i.sub.3 =0,1
and:
The computation of the metric of r.sub.1 . . . r.sub.8 in S.sub.i,j makes it necessary to compute metrics in the 4 8-D sub-sets E.sub.l.sup.(4) E.sub.l'j.sup.(4) (Sum of the metric of (r.sub.1 r.sub.2 r.sub.3 r.sub.4) in E.sub.l.sup.(4) and that of (r.sub.5 r.sub.6 r.sub.7 r.sub.8) in E.sub.l'j.sup.(4)). The minimum of the 4 metrics gives the 8-D metric in S.sub.i,j, M.sub.i,j.sup.(8).
For each 8-D block, the metrics in each sub-set S.sub.i,j are detected and computed, which metrics will be fed to the Viterbi decoder. These metrics are also the metrics of the trellis branches during the transitions 1, 2, . . . ,N+1.
Still in the first stage, the second decoding step is carried out. The sub-set 222 carries out a conventional Viterbi decoding of the received symbol sequences. In this manner is obtained the decoded optimum sequence (hard decision) of the row:
I.sup.(.nu.) =I.sub.1.sup.(.nu.), . . . I.sub.7N+4.sup.(.nu.),I.sub.7N+5.sup.(.nu.), . . . I.sub.8N+8.sup.(.nu.) and the decoded LSB bit sequence:
i.sup.(.nu.) =i.sub.1.sup.(.nu.), . . . i.sub.8N+8.sup.(.nu.) and the sequence of the corresponding 8-D sub-sets.
The sequence of the states which correspond to the decoded states is:
.sigma..sup.(i) =.sigma..sub.0.sup.(i), . . . .sigma..sub.N+1.sup.(i) which corresponds to N+1 transitions or branches, with .sigma..sub.0.sup.(i) =.sigma..sub.N+1.sup.(i) =0 which are the initial and final zero states. The vector of the state metric M.sub.j.sup.(i) (.sigma.) is stored for each state .sigma.=0, . . . 7 and for each instant j=1, . . . N+1. Finally, the surviving paths in a Table are stored. All these results produced by the Viterbi decoder 222 are used for computing the reliability.
During the third step, the reliability of each symbol I.sub.k.sup.(.nu.) or of each bit i.sub.k.sup.(.nu.) of the decoded sequence I.sup.(.nu.) with k=1, . . . 8N+8 is computed in the sub-set 224. The reliability features the quality of the decoded symbols (probability of exactness). This reliability may be written as:
The reliability of a symbol of the k.sup.th order is written as: ##EQU10##
where D.sup.(.nu.-1) is the sequence of input symbols and where C(I.sub.k.sup.(.nu.)) is the set of codewords corresponding to a 4-AM symbol near to I.sub.k.sup.(.nu.). The reliability F.sub.k.sup.(.nu.) may be written as: ##EQU11##
By taking the main term of the sum, one may write: ##EQU12##
This minimum gives maximum correspondence with the error path producing a decoded 4-AM symbol which is near to the symbol I.sub.k.sup.(.nu.). This definition of the reliability is also that of the bits i.sub.k.sup.(.nu.). In fact, a symbol near to I.sub.k.sup.(.nu.) corresponds to a bit i which is the complement of i.sub.k.sup.(.nu.).
The computation of the reliability takes place according to the following algorithm.
The sequence I.sub.k.sup.(.nu.) decoded by the Viterbi decoder corresponds to a path in the trellis having a length of N+1. The computation algorithm for computing the reliability F.sub.k.sup.(.nu.) of the decision I.sub.k.sup.(.nu.) for k=1, . . . 8N+8 is the following:
The reliability of the decision I.sub.k.sup.(.nu.) for k=1, - - - 8N+8, or of the bit i.sub.k.sup.(.nu.) for k=1, - - - 8N+8 is carried out in 2 steps. The first step consists of computing the reliability compared with the error paths that correspond to the parallel transitions, and the second step consists of computing the reliability compared with error paths of the trellis. The final reliability is the lower of the two.
First the reliability FP due to the parallel branches is computed. The processing is carried out block by block on the symbol sequence D.sub.k.sup.(.nu.-l) and I.sub.k.sup.(.nu.). Each processing makes it possible to compute the reliabilities due to parallel branches of the 8 symbols (D.sub.7l+1.sup.(.nu.-l), - - - - ,D.sub.7l+7.sup.(.nu.-l), D.sub.7N+5+l.sup.(.nu.-l)) which corresponds to the 1.sup.st transition (I=0, . . . . ,N-1) and the 8 symbols (D.sub.7N+1.sup.(.nu.-l), - - - - ,D.sub.7N+4.sup.(.nu.-l), D.sub.8N+5.sup.(.nu.-l), . . . ,D.sub.8N+8.sup.(.nu.-l)), which corresponds to the (N+1).sup.th transition (the one that closes the trellis). as the parallel branches of the trellis are allocated to 8-D sub-sets S.sub.i,j, this reliability is also the reliability of the decision I.sub.k.sup.(.nu.) in the 8-D sub-set containing the decoded block which corresponds to I.sub.k.sup.(.nu.) (the sequence of the decoded 8-D sub-sets is produced by the Viterbi decoder).
S.sub.i (r.sub.1, . . . r.sub.8) is the block (D.sub.1.sup.(.nu.-l), . . . ,D.sub.7.sup.(.nu.-l), D.sub.7N+5.sup.(.nu.-l)), for example, and S.sub.i,j the decoded 8-D sub-set corresponding to the detected 4-AM symbols (d.sub.1, . . . d.sub.8)=(I.sub.1.sup.(.nu.), . . . ,I.sub.7.sup.(.nu.),I.sub.7N+5.sup.(.nu.)), it may be shown that the computation of the reliabilities r.sub.k (for k=1, . . . 8) in S.sub.i,j boils down to computing the reliabilities of (r.sub.1, r.sub.2, r.sub.3, (1-2Y.sub.1)r.sub.4, r.sub.5, (1-2Y.sub.2)r.sub.6, (1-2Y.sub.3)r.sub.7, (1-2(Y.sub.1 .sym.Y.sub.2 .sym.Y.sub.3))r.sub.8) in the sub-set S.sub.o,j' with j'=j.sym.Y.sub.1 .sym.Y.sub.2 .sym.Y.sub.3, and i=8Y.sub.3 +4Y.sub.2 +2Y.sub.1. Thus, in all the cases this boils down to computing the reliabilities in S.sub.0,0 or S.sub.0,1, which makes the algorithm simpler.
FIG. 14 gives a representation in a trellis of the sub-sets S.sub.0,1 and S.sub.0,1 where each path in the trellis corresponds to a sub-set having the form B.sub.i1 B.sub.i2 . . . B.sub.i7 C.sub.2j8+i8.
The algorithm for S.sub.0,0 will be described, that is, S.sub.i,j =S.sub.0,0, for computing the reliabilities of the decision d.sub.k for k=1, . . . 8:
First the computation of the 2-D metrics takes place:
where
M.sub.k,i is the metric of r.sub.k in B.sub.i for k=1, . . . 7; and
M.sub.8,i is the metric of r.sub.8 in C.sub.i.
In the case where the computation of the reliabilities is performed for S.sub.0,1, M.sub.8,i is computed in C.sub.2 and C.sub.3 (i=2, 3).
Thus the nearest path from (r.sub.1, . . . r.sub.8) is sought in S.sub.0,0 :
The upper part and the lower part of the trellis of S.sub.0,0 are considered separately. In the upper trellis is computed M(0,k)=min (M.sub.0,0 (k), M.sub.1,1 (k)) for k=1, 2, 3
The bits (i.sub.1, . . . i.sub.8) giving the minimum value are stored, with i.sub.1 =i.sub.2, i.sub.3 =i.sub.4, i.sub.5 =i.sub.6, i.sub.7 =i.sub.8, in the Table [i(0,1), . . . i(0,8)] and: ##EQU13## is computed.
In the lower trellis, M(1,k)=min (M.sub.0,1 (k), M.sub.1,0 (k)) is computed for k=1,2, 3,
The bits i.sub.1 . . . i.sub.8 corresponding to the minimum in [i(1,1), - - - i(1,8)] with i.sub.1 =i.sub.2,i.sub.3 =i.sub.4,i.sub.5 =i.sub.6,i.sub.7 =i.sub.8 are stored.
There is verified whether the sequences [i(0,1), . . . i(0,8)] and [i(1,1), . . . i(1,8)] are two valid sequences. The parity bits p(0) and p(1) are computed for the sequences [i(0,1), i(0,3), i(0,5), i(0,7)] and [i(1,1), i(1,3), i(1,5), i(1,7)], respectively. For k=0, 1, if p(k)=0, the corresponding sequence belongs to the trellis (or S.sub.0,0), if not the sequence will be modified.
Differences of 2-D metrics are computed:
Then the minimum of 4 metrics is computed for each of the two upper and lower trellises (q=0, 1, respectively): ##EQU15##
The index k giving the minimum in k.sub.min (q) is stored and the second minimum .DELTA..sub.2 (q) is computed.
If the parity bit p(q)=1, the bits (i(q, 2 k.sub.min (q)-1), i(q, 2k.sub.min (q)) are complemented and the metric MET (q) of .DELTA.(q) is incremented. This operation is carried out for q=0 (upper trellis) and q=1 (lower trellis).
Then .DELTA..sub.min =.vertline.MET(0)-MET(1).vertline. is computed and the index c (0 or 1) is stored giving the lower value of MET(0) and MET(1).
The reliabilities FP(1), . . . ,FP(8) of (d.sub.1, . . . d.sub.8) are initialized in S.sub.0,0 :
where FP(k) is the reliability of d.sub.k in S.sub.0,0.
Thereafter, the reliabilities FP(k), k=1, . . . 8 are updated:
For k=1, . . . 8 with i(c,k).noteq.i (1-c, k):
FP(k)=min [FP(k), .DELTA..sub.min ]
For k=1, 2, 3, 4:
FP(2k-1)=min [FP(2k-1), A.sub.k ]
if i(0, 2k-1)=i(1, 2k-1)
FP(2k-1)=min [FP(2k), A.sub.k ] if i (0,2k)=i(1,2k)
with
The reliability caused by the error paths of the trellis (FIG. 15) is determined. Consider the decoding of a row (step 300).
One starts from:
I.sub.k.sup.(.nu.) which is the sequence of 4-AM symbols decoded by the Viterbi decoder for k=1, . . . 8N+8;
M.sub.k.sup.(.nu.) (.sigma.)=which is the metric of the state .sigma. at the instant k (k.sup.th transition) for k=1, . . . N+1.
D.sub.k.sup.(.nu.-1) which are the input symbols (produced by the preceding iteration decoder) for k=1, . . . 8N+8,
and the array of the reliabilities F.sup.(.nu.) =(F.sub.k.sup.(.nu.), k=1, . . . 8N+8) to FP.sup.(.nu.) =(FP.sub.k.sup.(.nu.), k=1, . . . 8N+8) or FP.sub.k.sup.(.nu.) is the reliability of I.sub.k.sup.(.nu.) caused by the parallel transitions (step 301 in FIG. 15).
For k=N+1, . . . 2, where k corresponds to one instant (index of the transition), the following operations are carried out:
a) based on the state of the coder after the k.sup.th transition in the decoded path .sigma..sub.k.sup.(.nu.), the state .sigma..sub.k-1.sup.(.nu.) is determined after the (k-1).sup.th transition of the decoded path and the 7 other precursor states of .sigma..sub.k.sup.(.nu.), that is, .sigma..sub.j,k-1.sup.(.nu.), j=1 . . . 7 (step 304). Therefore, the values of .sigma..sub.k.sup.(.nu.) for k varying from 1 to N+1 are produced by the Viterbi decoder, whereas the values of .sigma..sub.j,k-1.sup.(.nu.) may be stored in a memory.
Based on metrics of the states .sigma..sub.1,k-1.sup.(.nu.), .sigma..sub.2,k-1.sup.(.nu.), . . . .sigma..sub.7,k-1.sup.(.nu.) and .sigma..sub.k.sup.(.nu.) computed and stored in the Viterbi decoder, for k=2, . . . N+1, and which are denoted ##EQU16##
the 7 cumulated metrics of the state .sigma..sub.k.sup.(.nu.) are computed for the 7 paths coming from the 7 states .sigma..sub.j,k-1.sup.(.nu.), j=1, . . . 7. These 7 cumulated metrics are:
.delta.(j)=M.sub.k-1.sup.(.nu.) (.sigma..sub.j,k-1.sup.(.nu.))+MET(.sigma..sub.j,k-1.sup.(.nu.) .fwdarw..sigma..sub.k.sup.(.nu.)), where MET(.sigma..sub.j,k-1.sup.(.nu.) .fwdarw..sigma..sub.k.sup.(.nu.)) is the metric of the transition from the state .sigma..sub.j,k-1.sup.(.nu.) to the state .sigma..sub.k.sup.(.nu.) which is also the metric of the 8-D sub-set allocated to this transition. These metrics are stored in a memory during the Viterbi decoding (step 306).
The difference between the optimum metric and each of the cumulated metrics is computed:
where M.sub.k.sup.(.nu.) (.sigma..sub.k.sup.(.nu.)) is the optimum metric of the state .sigma..sub.k.sup.(.nu.).
Thereafter, the 7 surviving precursors to the state .sigma..sub.k.sup.(.nu.) are examined. A step back is made to the survivor of the j.sup.th order, from .sigma..sub.k.sup.(.nu.) to .sigma..sub.j,k-1.sup.(.nu.). Then each survivor of the j.sup.th order of the state .sigma..sub.j,k-1.sup.(.nu.) is examined until the initial state .sigma.=0, which consists of making the index of the transition vary from k to 1.
To reduce the complexity, the 7 survivors of the state .sigma..sub.j,k-1.sup.(.nu.) may be examined up to the state of the survivor at the instant k-L instead of the instant 1, thus a fixed number of transitions. For L=3, the degradation of the performance is negligible.
The 8 4-AM symbols allocated the k'.sup.th transition of the survivor of the j.sup.th order are compared with the 8 decoded symbols for k' which varies from k to 1, or from k to (k-L) in the second case. If the decoded symbol and the symbol of the k'.sup.th transition of the survivor j of the same rank are adjacent, the reliability of the decoded symbol is replaced by .DELTA.(j) if the latter is lower than this reliability (step 312).
The Table of the symbols I.sub.k.sup.(.nu.) which are adjacent I.sub.k.sup.(.nu.), which corresponds to the minimum, for k varying from 1 to 8N+8, and, with each updating of the reliability of one symbol, its adjacent symbol is updated by replacing it by the corresponding 4-AM symbol which relates to the transition of the k'.sup.th order of the survivor j.
In the end, the reliabilities F.sub.k.sup.(.nu.) of the decoded symbol I.sub.k.sup.(.nu.) and of the adjacent corresponding symbol I.sub.k.sup.(.nu.) for k=1, . . . 8N+8 (step 326) are obtained.
The reliability is thereafter normalized during the fourth step to allow of the computation of the soft decision D.sub.k.sup.(.nu.) for k=1, . . . 8N+8. Three methods can be used for computing the normalized reliability F.sub.k.sup.norm(v). One may compute: either
or
or
where F is equal to the average of F.sub.k.sup.(.nu.) computed of the whole reliability matrix, .beta..sub.1 and .beta..sub.2 being constants verifying F=.beta..sub.1 (1-.beta..sub.2).
Subsequently, during the fifth step, soft- non-weighted decision are computed (sub-set 226, FIG. 13).
The soft decision D.sub.k.sup.(.nu.) is computed on the basis of the optimum decision I.sub.k.sup.(.nu.) given by the Viterbi decoder, of its normalized reliability F.sub.k.sup.norm(v) and of the sequence of the 4-AM symbols I.sub.k.sup.(.nu.) obtained previously. The 4-AM symbol I.sub.k.sup.(.nu.) is an adjacent symbol to the symbol I.sub.k.sup.(.nu.), that is .vertline.I.sub.k.sup.(.nu.) -I.sub.k.sup.(.nu.) .vertline.=2. it corresponds to the 4-AM symbol which is most likely to occur after the symbol I.sub.k.sup.(.nu.). The symbol D.sub.k.sup.(.nu.) is given by:
where the function sgn is defined by: ##EQU17##
Thus, the symbol D.sub.k.sup.(.nu.) corresponds to a symbol situated at the distance F.sub.k.sup.norm(v) from the decision threshold between I.sub.k.sup.(.nu.) and I.sub.k.sup.(.nu.). As E(F.sub.k.sup.norm(v))=1, the symbols D.sub.k.sup.(.nu.) will be centered around 4-AM symbols.
To improve performance, during a sixth step D.sub.k.sup.(.nu.) is weighted with the symbols D.sub.k.sup.(0) received through the channel which are stored in the memory 20 for computing D.sub.k.sup.(.nu.) :
D.sub.k.sup.(.nu.) =.alpha..sub.v D.sub.k.sup.(.nu.) +(1-.alpha..sub.v)D.sub.k.sup.(0) where .alpha..sub.v is a weight factor. For example: .alpha..sub.1 =0,6; .alpha..sub.2 =0,9; .alpha..sub.v =1 for v greater than 1. The object is to reduce the effect of error propagation during the first iterations. The steps 5 and 6 are carried out together in the sub-set 226.
Secondly, consider the operation of the second stage (path 2) for the decoding of the bits j. The bits j, thus MSB bits of the 4-AM symbols are coded with the parity code applied to each row and each column of the matrix of the product code. This is realized when the trellis is closed. The decoding is an iterative decoding as for the bits i.
FIG. 16 represents the general circuit diagram of a stage comprising decoding means 22.sub.1 for decoding the parity code of the MSB bits of the transmitted 4-AM symbols. They comprise:
a decoder 322 for decoding the parity code which gives hard decisions;
a sub-set 324 for computing the reliability of the decisions;
a sub-set 326 for computing soft decisions.
For the first iteration (m=1), the symbols x.sub.k.sup.(0) are the received symbols on the output of the channel, that is:
(D.sub.1.sup.(0), . . . D.sub.7N+4.sup.(0),D.sub.8N+5, . . . D.sub.8N+7.sup.(0)).
FIG. 17 gives a representation in a trellis of the 7N+7 bits (j.sub.1, . . . j.sub.7N+4,j.sub.8N+5,j.sub.8N+6,j.sub.8N+7) coded with the parity code. In this trellis, any path from point I to point F corresponds to a codeword having length 7N+7. The decoding of a block of 7N+7 symbols x.sub.k.sup.(m-1) for the m.sup.th rank iteration is allocated in 3 steps.
During the first step (step 322), a hard decision decoding is made of x.sub.k.sup.(m-1). A threshold decision is applied symbol by symbol to these symbols in the sub-set B.sub.i.sbsb.k, where i.sub.k for k=1, . . . 7N+4, 8N+5, 8N+6, 8N+7 is the sequence of the LSB bits of the 4-AM symbols estimated by the iterative decoding of the first stage after the convergence. This threshold decision produces a first bit estimate j.sub.k.sup.(m) with j.sub.k.sup.(m) =0 (1, respectively) if the decision in B.sub.i.sbsb.k is positive (negative, respectively).
Subsequently, for each symbol x.sub.k.sup.(m-1) is computed the absolute value of the distance d(x.sub.k.sup.(m-1),t.sub.k.sup.(m-1)) separating this symbol from the decision threshold t.sub.k.sup.(m-1) in the sub-set B.sub.i.sbsb.k, where the threshold in B.sub.0 ={3,-1} (B.sub.1 ={1,-3}, respectively) is equal to +1 (-1, respectively) and the minimum .DELTA. for k of the distance d(x.sub.k.sup.(m-1),t.sub.k.sup.(m-1)) is computed and so is the second minimum .DELTA..sub.2.
Finally, the parity bit p of the bits j.sub.k.sup.(m) is computed. If the parity is satisfactory (p=0), the sequence of the bits j.sub.k.sup.(m) is the optimum sequence. If not, the bit j.sub.k.sbsb.min.sup.(m) is complemented where k.sub.min is the index providing the minimum .DELTA. of d(x.sub.k.sup.(m-1),t.sub.k.sup.(m-1)).
During the second step, the computation of the reliabilities (step 324) is made. The reliability of the decision j.sub.k.sup.(m) is given by:
Subsequently, the reliability is normalized according to:
where FJ is the average of the reliabilities FJ.sub.k.sup.(m).
During the third step, the computation of the soft decision x.sub.k.sup.(m) is made (step 326). This decision is obtained as a function of t.sub.k.sup.(m),j.sub.k.sup.(m), FJ.sub.k.sup.norm(m) via:
x.sub.k.sup.(m) =t.sub.k.sup.(m) +2 sgn(1-2j.sub.k.sup.(m)).times.FJ.sub.k.sup.norm(m) where sgn(.) is the sign function.
The invention has just been described in the case of a systematic convolutional code of rate 7/8. A person of ordinary skill in the art may apply the same coding and decoding principles to other systematic convolutional codes of rate P/(Q.M) combined with other multidimensional amplitude modulations having dimension Q and having 2.sup.M states.
Claims
We claim:
1. A method of protecting input data implemented in a digital transmission system, the method comprising a coding phase for said data and an iterative decoding phase, the coding phase comprising a first step for performing a systematic convolutional trellis coding permitting of the iterative decoding combined with a second step for assigning the coded data to digitally modulated symbols, characterized in that during the first step the systematic trellis coding has a coding rate P/(Q.M), where M, P and Q are integers with Q and M being greater than 1, the systematic convolutional code being used for generating a product code in blocks with trellis closure by the addition of redundant data, the product code being formed by components generated by row coding and column coding of a matrix that combines the coded data via the systematic convolutional code, whereas the second step combines the product code with a multidimensional amplitude modulation having dimension Q that has 2.sup.M states, the iterative decoding being a block decoding.
2. The method as claimed in claim 1, characterized in that the rate is equal to 7/8, the modulation being an 8-D modulation having 8 dimensions.
3. A digital transmission system with input data protection, comprising coding means of said data and iterative decoding means, the coding means comprising: a first sub-set for performing a systematic convolutional trellis coding permitting of the iterative decoding and a second sub-set for assigning the coded data to digitally modulated symbols, characterized in that the first sub-set utilizes a systematic convolutional trellis coding having a coding rate P/(Q.M), where M, P and Q are integers with Q and M being greater than 1, the systematic convolutional code being used for generating a product code in blocks with trellis closure by the addition of redundant data which comprise at least one parity code bit, the product code being formed by components generated by row coding and column coding of a matrix that combines the coded data via the systematic convolutional code, whereas the second sub-set combines the product code with a multidimensional amplitude modulation having dimension Q that has 2.sup.M states, the iterative decoding being a block decoding.
4. The system as claimed in claim 3, characterized in that the coding means comprise a means called state machine for defining successive states of the coder and producing the trellis closing redundancy symbols.
5. The system as claimed in claim 3, characterized in that the rate is equal to 7/8, the modulation being an 8-D modulation having 8 dimensions, the systematic convolutional coding means coding seven input symbols into eight output symbols by adding one redundancy bit.
6. The system as claimed in claim 5, characterized in that the systematic convolutional coding means comprise two shift-cell stages, the output symbols being obtained by linearly combining the data coming from the shift cells.
7. A system as claimed in claim 3, characterized in that the iterative decoding means comprise at least two paths operating in succession: along a first path, the system carries out with each iteration of the path a first iterative decoding with: a) computing means for computing hard decision which relate to the systematic convolutional code, b) computing means for computing first reliabilities of the hard decisions associated with each multidimensional modulation sub-set, and second reliabilities associated to the trellis of the systematic convolutional code, c) selecting means for selecting minimum reliabilities between the first and second reliabilities of each decision, and d) computing means for computing soft decision used for the next iteration of the first path as a function of selected minimum reliabilities and hard decisions; and along a second path, the system utilizes for each iteration of the path: a) computing means for computing hard decisions which relate to the parity code, b) computing means for computing third reliabilities for each hard decision of the second path as a function of hard decision of the first path, and c) computing means for computing soft decisions as a function of the third reliabilities, soft decisions coming from the preceding iteration of the second path and hard decisions from the firth path.
Patent Citations (4)
Non-Patent Literature (1)
- "Near Shannon limit error-correcting coding and decoding: Turbo-codes (1)" by C. Berrou et al, Proceeding of ICC '93, Geneva, May 1993, pp. 1064-1071 .