"A method for trellis coding a logarithmic distribution of constellation points"
The present invention relates to a method for trellis coding a logarithmic distribution of constellation points, and in particular, though not limited to a method for applying trellis coding to such a system of constellation points for a pulse code modulation (PCM) modem which uses A-Law or μ-Law codecs for coding voltage levels of analog signals outputted by the modem.
The application of known trellis coding for example, V.34 type trellis coding as recommended by International Telecommunications Union (ITU) - Telecommunications Division to systems with a logarithmic distribution of constellation points such as PCM modems which use A-Law or μ-Law codecs is unsatisfactory. Typical known methods which apply trellis coding to such logarithmic distribution of constellation points cause problems with coding gain. A-Law and μ-Law codecs have 256 analog output levels. These levels are divided into a number of groups of levels with nominally equal intervals between successive levels in a group. The group of lowest levels have the smallest intervals between the respective successive levels, and the intervals between the levels in the group of lowest levels are equal. The group of lowest levels is followed by a group of the next levels above the levels of those of the group of lowest levels, and the intervals between the respective successive levels in this group are also equal and of value twice the value of the interval between the levels in the lowest levels group. The group of second lowest levels is then followed by a group of third lowest levels and so on, in each case, the intervals between the levels in the respective groups being similar, but the intervals between the levels in the respective groups in each case is twice the intervals between the levels in the immediately lower group. In general, with some minor exceptions the groups of levels contain similar numbers of levels.
In conventional n-dimensional trellis coding, the number of points in the constellation is doubled in n-dimensions , for example, a 32 point 2-dimensional constellation becomes a 64 point 2-dimensional constellation for 2-dimensional code, or a 1,024 point 4-dimensional constellation becomes a 2,048 point 4-dimensional constellation for a 4-dimensional code. The following example illustrates how a conventional application of trellis coding is not an ideal method for increasing performance in, for example, A-Law and/or μ-Law codec. In an A-Law or μ-Law codec, the top 128 levels are divided into four groups of 32 levels. For a 16 state 4-dimensional trellis code used in V.34 modems, if the top 128 levels were used as constellation coordinates at a sample rate of 8kHz, the following holds :
a 128 point uncoded 1-dimensional constellation gives a bitrate of 56kbit/sec.
a 128 point conventionally coded 4-dimensional constellation gives 54kbits/sec with approximately 4dB signal to noise ratio (SNR) coding gain.
a 112 point uncoded 1-dimensional constellation, obtained by dropping half of the lowest 32 levels, gives a bitrate of 54.46kbits/sec with an SNR gain of 6dBs.
Accordingly, as can be seen from this example, conventional application of trellis coding to such a constellation is counter-productive.
There is therefore a need for a method for trellis coding a logarithmic distribution of constellation points, which overcomes this problem.
The present invention is directed towards providing such a method .
According to the invention there is provided a method for trellis coding a logarithmic distribution of constellation points, wherein the trellis coding is applied only to the lower level points of the constellation whose interval from their respective next immediate lower level point is less than a predetermined value .
In one embodiment of the invention the points are initially in the form of an input bit stream, and the method comprises the step of generating an index (In) from the input bit stream for each point for determining if the point is to be trellis coded.
Preferably, the generated index (In) lies between zero and a maximum index (Imax), where the maximum index (Imax) is equal to one less than the highest code value divided by two .
Advantageously, a maximum trellis code index (Imaxt) is generated, the maximum trellis code index being a function of the predetermined value of the interval between the levels below which the points are to be trellis coded. Ideally, the maximum trellis code index (T-m )is equal to one less than the highest trellis code divided by two.
In another embodiment of the invention the generated index (In) is compared with the maximum trellis code index (Imaxt) for determining if the point from which the generated index (In) has been generated is to be trellis coded.
In another embodiment of the invention one bit is selected from the input bit stream and passed to a reflection means when the generated index (In) is determined to be greater than the value of the maximum trellis code index (Imaxt), and the point is not to be trellis coded.
In a further embodiment of the invention when the value of the generated index (In) is determined to be less than or equal to the maximum trellis code index (Imaxt) three bits are fed from the input bit stream for the first point to be trellis coded to a trellis coding means for coding thereof, and for every fourth such point thereafter three more bits are fed to the trellis coding means for trellis coding, and the trellis coded outputs from the trellis coding means are fed to the reflection means .
In one embodiment of the invention the trellis coding means generates two 2-dimensional subsets or four 1-dimensional reflections from each three bits received from the input bit stream, the two 2-dimensional subsets or the four 1-dimensional reflections are then fed to the reflection means .
In another embodiment of the invention the generated index (In) is transformed to form a transform number
(Pn).
Preferably, the 1-dimensional reflections generated by the trellis coding means is applied to the transform number (Pn) to generated a selector number (Qn) for selecting an output level corresponding to the point to be transmitted.
Advantageously, the four 1-dimensional reflections outputted by the trellis coding means are sequentially applied to the transform number in the reflection means for generating respective selector numbers for the point corresponding to the generated index (In) and for the next three points, the generated index (In) of which is less than or equal to the maximum trellis code index
( -"-max ) '
In another embodiment of the invention the transform number (Pn) is equal to twice the value of the generated index (In) less twice the sum of twice the generated index (In) + 1 multiplied by the modulo 2 of the generated index (In) where the modulo 2 of the generated index (In) is the remainder when the generated index (In) is divided by two.
In a further embodiment of the invention the output level to be transmitted is determined by the selector number from a look-up table .
In one embodiment of the invention the reflection means generates at least one reflection of each point. Preferably, the reflection means generates four reflections of each point one in each subset.
In one embodiment of the invention the logarithmic distribution of constellation points are voltage levels to be transmitted by a pulse code modulation modem.
Further the invention provides a method for trellis coding a logarithmic distribution of constellation points using a convolutional coder, wherein each bit of the convolutional code or output is used to determine a trellis code subset via a one dimensional reflection
Additionally, the invention provides apparatus for trellis coding a logarithmic distribution of constellation points, wherein the apparatus operates according to the method of the invention.
The invention will be more clearly understood from the following description of a preferred embodiment thereof which is given by way of example only with reference to the accompanying drawing, namely, Fig. 1 which illustrates a block representation of the method for trellis coding a system with a logarithmic distribution of constellation points, which in this case is a system used in a PCM modem which uses μ-Law codec .
TABLE 1
Simplified μ-Law
Min interval : Clmin = 8
Level no. In-interval yn: Output Levels used Level Differ Code
Value used ence yn = yn-1 +ln/2 + 1 N-1/2 pos. neg.
0 0 4.5 don't
0 1 0 use
1 1 1 1 -1
2 1 2 2 -2
3 1 3 3 -3
4 2 4.5 4.5 -4.5 9 1,-1
5 2 6.5 6.5 -6.5
6 2 8.5 8.5 -8.5
7 2 10.5 10.5 -10.5
8 4 13.5 13.5 -13.5 8 3,-3
9 4 17.5 17.5 -17.5
10 4 21.5 21.5 -21.5 10 5,-5
11 4 25.5 25.5 -25.5
12 8 31.5 31.5 -31.5 8 7,-7
13 8 39.5 39.5 -39.5 8 9,-9
14 8 47.5 47.5 -47.5 8 11,-11
15 8 55.5 55.5 -55.5 12 13,-13
16 16 67.5 67.5 -67.5 16 15,-15
17 16 83.5 83.5 -83.5 16 17,-17
18 16 99.5 99.5 -99.5 16 19,-19
19 16 115.5 115.5 -115.5 24 21,-21
20 32 139.5 139.5 -139.5 32 23,-23
21 32 171.5 171.5 -171.5 32 25,-25
22 32 203.5 203.5 -203.5 32 27,-27
23 32 235.5 235.5 -235.5 29,-29 Table 1 illustrates a code, which is similar to a μ-Law code with the exception that fewer groups of intervals and fewer intervals per group are provided. If for example :
(a) line conditions dictate that a minimum uncoded interval UImin of approximately 16 is required to obtain an acceptable error rate, and
(b) the coding gain should be approximately 6dBs (excluding the added redundancy), then this would require that an interval of 8, with a coding gain of about 6dBs giving twice the effective interval, would be acceptable (CImin=8)
In the method according to the invention the voltage levels to be coded are initially selected, and the following procedure sets out how to select the levels for coding. Starting at the highest level, all levels which are separated by an interval from their adjacent level, which is greater than an interval CImin from the previously accepted level are accepted. If the lowest level accepted is less than 0.5 CImin, it should also be discarded. This is because both positive and negative values of each level are used and need to be distinguished from each other. Thus, the smallest positive level should be at least CImin above its negative equivalent. It should however be noted that in the case of A-Law codes, an extra point near zero is discarded. It is possible to use this extra point by changing the mapping scheme, although this would require two different schemes, one for μ-Law and one for A-Law codes .
In this way, the values of the levels which are to be used are arrived at. The levels are divided into two categories, namely, the first category which takes all levels from the lowest level to the lowest level below the first interval greater than or equal to UImin. Small adjustments to the value of the levels used may be applied, for example, to distribute the levels more widely, particularly, at the end points. However, neither CImin for the lower category nor UI^ for the upper category should be exceeded.
The codes are then assigned numbers consecutively starting at one for the lowest positive level and continuing in steps of two. The pairs of positive and negative levels are assigned the same code except that one is the negative of the other. This is carried out for the example in Table 1.
Referring now to Fig. 1 trellis coding of the signals will now be described. In accordance with the invention trellis coding is only applied to the lower category of levels, in other words the lower levels of which the intervals separating adjacent levels is less than or equal to a predetermined interval value . Trellis coding is carried out by a trellis coding means, namely, a convolutional coder, illustrated as block 1. When a point of the upper category is to be transmitted, it is transmitted without trellis coding and thus by-passes the convolutional coder 1. A preferred method for carrying out the trellis coding is as follows .
A Bit-to-index generator which is illustrated by block 2 takes the number of bits it requires from an input bit stream fed on a line 3 through a switch 4 and generates an index In which lies between zero and a maximum index Imax. The maximum index Imax is equal to the (highest code -l)/2. The Bit-to-Index generator 2 comprises a shell mapping scheme similar to that defined in International Telecommunications Union - Telecommunications Division recommendation V.34. Alternatively, the Bit-to-Index generator may be a base conversion from the binary input base (base 2) to an (Imx plus 1) output base, or any other suitable generator. The generated index In is then transformed or converted into a transform number Pn by block 5 as follows: Pn=2. Ia+l-2 ( 2. In+1) . ( In modulo 2 ) where In modulo 2 is the remainder when the generated index In is divided by two .
If any n levels are taken together they constitute an n-dimensional point with each 1-dimensional level being a coordinate . When a level belongs to the lower category, that is if the generated index In is less than or equal to a maximum trellis code index Imaxt, where the maximum trellis code index Imaxt=(highest trellis category code-l)/2, then trellis coding is required. The first level that belongs to this category is considered to be the first of n-dimensions . The next level that also belongs to this category is considered to be the second of n-dimensions and so on.
Block 6 compares the generated index In with the maximum trellis code index Imaxt. When block 6 determines that the generated index In is greater than the maximum trellis code index Imaxt one bit from the input bit stream on line 3 is fed through the switch 4 directly to a reflection means, illustrated by block 9, which is described below. The bit is transferred directly to the reflection block 9 through switches 7 and 8 under the control of block 6. On block 6 determining that the generated index In is less than or equal to the maximum trellis code index Imaxt the switches 7 and 8 are thrown, and bits are taken from the bit stream on the input line 3 and are fed through the switch 4 and the switch 7 to the convolutional coder 1. In this case when block 6 determines that the generated index In is less than or equal to the maximum trellis code index Imaxt, then for the first such point, and every fourth point thereafter three bits are taken from the input bit stream 3 and fed into the convolutional coder 1 and trellis coded, and are fed to the reflection block 9 through the switch 8 as will be described below.
Any trellis coding scheme can be applied in the convolutional coder 1, for example, the 16 state Wei trellis code which is used in V.34 may be used to trellis code the lower category levels . In this code 2-dimensional points are divided into four subsets. All the points at this stage, when Pn and the next trellis coded output Pn+i are combined belong to a single 2-dimensional trellis code subset. Each point must then be moved to the required subset. The correct subset is determined by the convolutional coder 1. The shell mapping algorithm in the Bit-to-Index generator 2 generates the index In on the basis of the required power of the point . In order not to change the power of the point, the point is reflected in the X and Y axes to transform the point into the required subset. This is carried out in the reflection block 9.
A reflection in the X axis in 2-dimensions, that is taking two consecutive lower category levels and considering them to be a 2-dimensional point and multiplying the first level by -1, brings the 2-dimensional point into the second trellis subset. A reflection in both axes, that is multiplying the first and second levels by -1, brings them to the third subset and a reflection in the Y axis, that is multiplying the second level by -1, brings them into the fourth and final subset. A 2-dimensional rotation could also be used to modify the subset, without changing the power, but rotations in 2-dimensions require both coordinates to be available at the time of rotation, which is more difficult to organise.
When it is determined by block 6 that the generated index In is less than or equal to the maximum trellis code index Imaxt, in other words that the point is found to be from the lower category, then for the first such point, (and every fourth such point thereafter) three bits are taken from the input stream and fed into the convolutional coder 1, as discussed above. This generates two 2-dimensional subsets or four 1-dimensional reflections. The first of these reflections is applied to the transform number Pn in block 9 to give a selector number Qn. The second is applied to the next index found to be from the lower category, the third to the third such and the fourth to the fourth such, and then the next index in the lower category generates a new set of rotations from three more input bits .
As discussed above if the generated index In determines that the point belongs to the upper category then one bit is taken from the input bit stream, if this bit is referred to as j, many mapping schemes are possible, but a simple scheme is to use this bit to select whether to multiply the transform number Pn by -1, that is Qn = Pn(2.j-1).
One of these two possible steps generates Qn which is used to select the level to be transmitted in block 10 from the codes of the look-up table of table 1.
One consequence of implementing this encoding scheme is that, ideally, the receiver needs to buffer enough symbols so that it can be sure to have received all 1-dimensional components of a number of 4-dimensional symbols before it can decode a trellis coded symbol, and thus output it. It is difficult to determine how long this needs to be, although the probability of given buffer size number being enough to decode the current symbol can be calculated. There are a few ways of overcoming this uncertainty. One is to provide a buffer large enough for the vast majority of cases, but periodically the buffer may be of insufficient size, to output an immediate decision, or a decision based on a reduced decoder delay, instead of a full Viterbi decision. Another is to deliberately insert a lower category level after a defined regular interval of higher category only levels. A third possibility is to insert trellis coded higher category points, also after a defined regular interval of higher category only levels. These points would allow a more robust decision to be made for a reduced decoder delay.