Note: Descriptions are shown in the official language in which they were submitted.
CA 0223801~ 1998-0~
WO 97/2039S . PCT/SE96/01555
A ~Jl~HoD AND AN ARRANGEMENT FOR MAK~NG FIXED LENGTH COD~S
TECHNICAL FIELD
The present invention relates to a method of making fixed length codes
more robust against bit errors. The invention also rel~tes to an arrangement
for carrying out the method.
DESCRIPTION OF THE BACKGROUND ART
Events can be coded in binary code words. A binary encoding method with
substantially uniform rate is shown in the US patent US 5,300,930. Often
one wants to code the information in as few bits as possible in order to
minimise the bandwidth required. Depending on the probability distribution
of the events it is possible to code the information in such a way that
events that occur rarely are coded with longer code words and events that
occur frequently are coded with shorter code words and the encoding is
done so that the decoder can distinguish between the different code words.
Such codes are called instantaneous.
Very efficient codes can be designed in this way and the method of coding
is called entropy coding.
However, assume that the transmission channel between the encoder and
decoder introduces bit errors. In this case probiems arise because the
decoder cannot with certainty decode the different variable length code
words since it is not possible to see where one code word starts and
CA 0223801~ 1998-0~
WO 97/20395 2 PCT/SE96/01555
another ends. Of course, this can have a devastating effect on the
interpretation of the received information.
Usually this problem is solved by means of channel coding, where controlled
redundancy is introduced in the channel encoder in such a way that the
channel decoder can detect and correct erroneous bits.
Using this method more bits have to be transmitted over the channel and
the channel bit rate increases as well as the complexity due to the channel
encoder and decoder. Moreover, at bit error rates that are higher than the
error correcting capacity of the channel coding, the decoded bit error rate
often becomes worse than the uncoded bit error rate. Such a threshold
exists for every code, either limited by the Shannon capacity formula or on
a restriction in acceptable delay due to channel coding.
One way to overcome some of the drawbacks with a variable length code,
in terms of bit error robustness, is to use a fixed length code. Here we lose
some efficiency because all code words have the same length independent
of the probability distribution of the events to be coded. However, once
synchron;sed, each code word can be decoded independent of any other
code word and this makes the code rather robust.
If we assume that the information to be transmitted represents a 'level'
monotonically increasing from a minimum value to a maximum value the
events represent discrete points on this level curve and each point is coded
with a fixed length code word.
A bit error in a code word causes a jump in the level curve and dependent
on which bit in the code word that is erroneous, the level jump becomes
smaller or larger. This means that some bit errors (at certain positions in the
code word) may cause an acceptable decoded level (small level error) while
other error bits in a code word cause a totally unacceptable level change.
CA 0223801~ 1 998 - o~
wo 97/20395 3 PCT/SE96/01555
The common way to improve the robustness to bit errors of a fixed length
code table is by means of Gray coding is to be found in the following two
books:
[1] ~ohn A.C. Bingham, "The Theory and Practice of Modem Design", John
Wiley & Sons, 1988 (pp. 65-66).
[2] E.A.Lee, D.G. Messerschmitt, nDigital Communication", Kluwer
Academic Publishers
Boston, 1988 (pp. 193).
A well known method to decrease the bit error sensitivity of a fixed length
code is by means of Gray coding which is shown in figure 1. Gray codes '
have the property that nearest neighbours are encoded into code words that
differ by only one bit, i.e. the Hamming distance is 1. This works fine for a
2-bit code 14 words) in a 2-dimensional signal constellation, where also the
Euclidean distance is at a minimum for code words with Hamming distance
= 1 .
In a 1-dimensional representation, when the code words represent a level,
the situation is different, as illustrated with the following 3-bit codes with 8levels .
A straight forward code and two Gray codes with associated bit error
distances are shown in Table 1. The distance d1 is the sum of the distances
obtained by changing one bit at a time in the code word. The mean distance
per bit is then d1 / 3 units.
CA 02238015 1998-05-15
WO g7/20395 4 PCT/SE96101555
Level Straight Code Gray Code 1 Gray Code 2
Code Disl~nce dl Code Distance d1 Code Dislal~ce dl
0 000 4+2+1=7 000 ~+1+3=9 0003+1+7=11
1 001 4~2+1=7 010 5+1+1=7 0101+1+5=7
2 010 4+2+1=7 011 5+1+1=7 1101+1+3=5
3 011 4+2+1=7 001 1+1+3=5 1003+1+1=5
4 100 4+2+1=7 101 1+3+1=5 1013~1~1=5
6 101 4+2+1=7 100 5+1+1=7 1111+1+3=5
6 110 4+2+1=7 110 5+1+1=7r0111+1+5=7
7 111 4+2+1=7 111 5+3+~=9'0013+1+7=11
Table 1.
Using a metric based upon the Euclidean distance, d1, or the squared
Euclidean distance, d2, we can define the following distances
1 M-l
p(m) dl(m)
n m~O
and
1 M-l
~2 =--~ p(m) d2(m)
n m=O
1 0 where
n is the number of bits in code word,
M is the number of code words,
plm) is the pdf (probability density function) of the level, m = 0, 1, ..., M-1,el is the mean error distance per bit and
~2 iS the mean squared distance (mse) per bit.
The mean error distance per bit is ~l = 713=2~33 units for all three codes.
Thus, for a uniform pdf for the level, nothing is gained with a Gray code
compared with the straight code. However, if the levels 3 and 4 (2,3,4 and
~;) are more common than the other levels a gain of the Gray code 1 (Gray
code 2) in the mean error distance is achieved.
CA 0223801~ 1998-0~
WO 97/20395 5 PCT/SE96/01555
SUMMARY OF THE INVENTION
This invention is about how to make fixed length codes more robust against
bit errors, in cases when the probability density function (pdf) has a peak
~not uniformly distributed). A considerable gain in mean squared error ~mse)
can be achieved in these cases, and the actual gain depends on the number
of bits in the code word and the actual pdf of the level.
PROBLEM DESCRIPTION
Introducing a bit error in the straight code in Table 1, the level jump may be
1, 2 or 4 units depending on the position of the erroneous bit. This is valid
for each of the 8 code words and the mean error distance is ~l = 7/3 =
2.33 units per bit. If the mse is used, the figure becomes ~2 = ~12+22+42)/3
= 7 units2 per bit. These values on ~1 and ~2 are independent of the actual
pdf, and therefore this straight code may serve as a reference for other
codes.
Assuming a uniform pdf for the Gray code 1 we get a mean error distance of
~1 = 2*~9+7+7+5)/(8*3) = 7/3 = 2.33 units per bit which is equal to the
straight coding. The mse becomes ~2 = 2~i/3 = 8.33 units2 per bit.
The corresponding figures for the Gray code 2 are; mean error distance ~1 =
7/3 = 2.33 units per bit and mse ~2 = 27/3 = 9 units2 per bit.
Thus, nothing is gained by using Gray coding compared to straight coding if
the level pdf is uniform. On the contrary, if mse is chosen as the metric there
is a performance loss.
However, if we have a pdf with a peak in the central part of the coding table
a performance gain can be anticipated with the Gray code tables.
CA 0223801~ 1998-0~
WO 97/20395 6 PCT/SE96/01555
Still, the minimum distance and the minimum squared distance are for the
Gray code tables 5/3 = 1.67 units per bit and 1113 = 3.67 units2 per bit,
respectively, and these values may be too large to be acceptable and they do
not represent the minimum values that can be achieved.
Sometimes the pdf does not have a peak at the central part but may have
another shape, for example, two peaks on either side of the central part of
the level curve. To cope with this situation another design method is required
to build a bit error robust fixed length code tsble.
The chrominance ~colour difference~ components represented by the fixed
length tables usually have a very pronounced peak, therefore the invented
code should be suitable for improving the robustness to bit errors in this
context .
BEST MODES OF CARRYING OUT THE INVENTION
A mobile telephone radio communication system is shown in figure 2. A radio
base station BS transmits information to and from a mobile radio terminal
MS. The radio connection is shown in the figure as a zig-zag symbol between
the radio base station BS and the mobile radio terminal MS.
Figure 3 is a flow chart illustrating how information is transferred from the
radio base station BS to the mobile radio terminal MS of figure 2. A block
101 illustrates an input device which in the embodiment is e.g. a video
camera connected to the radio base station shown in figure 2. A block 10Z
illustrates a digitiser connected to the input device. An encoder 103 is in
accordance with the invention connected to the digitiser. A transmitter is
illustrated with block 104. The blocks 102-104 are parts of the radio base
station BS. Block 105 illustrates the channel on which information is
transmitted from the radio base station BS to the mobile radio terminal MS.
The channel is a radio channel of 9.6 kbits/s disturbed by e.g. Rayleigh
,
CA 0223801~ 1998-0~
WO 97/20395 7 PCT/SE:96/01555
fading. Block 106 illustrates a receiver situated in the mobiie radio terminal
MS and a decoder is illustrated by block 107. Block 108 symboiises e.g. a
video monitor. The input device 101 comprises an information source that
generates a variable that is a function of time F(t), wherein a probability
density function for values of F(t) occurring in said information source has a
maximum. The digitiser 102 and the encoder 103 of the function F(t)
perform digitisation and encoding of F(t) into a function F'(t) by using a tablesuch that the Hamming distance between code words of F'(t) that are
adjacent to one another is lower for values of F(t) that are near the maximum
of the probability density function than for values of Flt) that are further
away from said maximum. The transmitter 104 transmits the information in
the function F'(t) over the channel 105. The information is received by the
receiver 106 as F"(t) because F'~t) has been disturbed by Rayleigh fading in
the channel 105. The decoder 107 decodes the received function F"(t) back
into a function F'"(t) which is similar to the original function F(t), by using a
table which is the inverse of the table in the encoder 103.
The earlier mentioned Gray code is characterised by the fact that the
Hamming distance for a code word to the closest neighbours is one. If the
code represents a level monotonicaliy increasing from a minimum value to a
maximum value the Hamming distance may not be the proper metric to use
for a robust code design. Rather, one should use a metric that reflects the
level change when the different bits in a code word change, such as the
Euclidean distance or the squared Euclidean distance (the mse).
The design method for the pdf with a peak is illustrated with a 3 bit code
table, the so called Baang-1 code. We assume that we know the pdf or at
least the position of the peak of the pdf representing the level curve.
The other code design method, suitable for more general pdf:s is illustrated
by a 4 bit code table, the so called Baang-2 code.
CA 0223801~ 1998-0~
WO 97/20395 8 PCTtSE96/01555
7.1 Pdf with a peak (Baang-1 code)
Here we want to minimise the distances for code words taken from a
particular code word, hereafter denoted the kernel, and outwards. The code
S words are taken in an order of increasing distance from the kernel.
7.1 .1 ) Initialise the code table.
7.1.1 .a) Pick the kernel, for example 111, and put it on that level position
that corresponds to the peak of the level pdf, in our case, say level 3.
Level Code Word
3 111 (kernel)
7.1.1.b) On either side of the kernel, insert two new code words with the
Hamming distance one to the kernel. In this case we change the leftmost bit
first and then the next bit in order. However, any order of bitchange can be
used .
Level Code Word Distance d1
2 011
3 111 1 +1 +?=?
4 101
7.1.1.c) The third bit, the rightmost bit of the kernel, is now changed and
the new code word is put on level 1 (or level 5)
Level Code Word Distance d1 d2
1 1 0
2 011
3 111 1+1+2=412+12+22=6
4 101
CA 0223801~ 1998-0~
WO 97120395 9 PCT/SE96/01555
With this initialisation we have packed all code words with the Hamming
distance one as close as possible ~in the ~uclidean distance sense) to the
kernel .
Should there be more than 3 bits in the code words, say n bits, the same
procedure is applied and the result is an initialisation of (n + 1 ) code words.
7.1.2) Continue to build the table.
7.1 .2.a) The next code word to consider is the one closest to the kernel
and with the maximum degree of freedom to design new code words in a
compact way.
Level 2 with the code word 011 has code words on each side, but level 4
with the code word 101 has a code word only on one side (111), and thus
has the maximum degree of freedom. This code word (101) is called the
1 :st reference.
Thus, changing the bits in the 1 :st reference we get the following table:
(here we use the same order for changing bits as was used in the
initialisation, but any other order can be used as well)
Level Code Word Distance d1 d2
1 1 0
2 011
3 111 1 +1+2--4 6
4 --> 101 1 t1 tZ=4 6
001
6 100
CA 02238015 1998-0~-15
W O ~712Q395 10 PCT~SE96/01555
If not the bit changed code word is in the table we add it as close as
possible to the reference word.
7.1.2.b) Following the principle in 2a) we now consider level 2 and choose
code word 011 as the 2:nd reference and get
Level Code Word Distance dl d2
0 010
1 1 0
2 --> 011 1+3+2--6 14
3 111 1+1 +2=4 6
4 101 1 + 1+2=4 6
001
6 100
7.1 .2.c) For the next reference to consider (110 or 001) there is no
difference in the distance to the kernel and the number of freedom is the
same and so 2a) does not give us the information how to proceed and any
side can be used.
In this example we stick to the symmetry principle and process that code
word that is on the opposite side of the kernel of the last processed code
word.
In this case it means level 6 with the reference word 001, and the result is
Level Code Word Distance d1 d2
0 010
1 1 0
2 011 1 +3+2z614
3 111 1+1+234 6
4 101 1+ 1+2--4 6
--> 001 1+3+2=6 14
6 100
7 000
CA 0223801~ 1998-0~
WO 97/20395 11 PCT/SE96/01555
7.1.3) All 8 code words are now associated with a level and we just
calculate the distance d1 (m) and mse d2(m) for the remaining 4 code
words.
~,
Table 2 shows the final result, the 3 bit Baang-1 code.
Straight Code Baang-1 Code
Code Distance Code Distance
dl d1 d2
o 000 4+2+1 =7 010 1 +7+2=10 54
001 4+2+1=7 110 1+5+2=8 30
2 010 4+2+1=7 011 1+3+2=6 14
3 011 4+2+1=7 111 1+1+2=4 6
4 100 4+2+1 =7 101 1 +1 +2-4 6
101 4+2+1 =7 001 1 +3+2=6 14
6 110 4+2+1=7 100 1+5+2=8 30
7 111 4+2+1=7 000 1+7+2=10 54
Table 2.
As can be seen from the table, the distance d2 for the straight code is 21
for each code word.
7.1.3) Te~ .alion of the table.
If a new code word designed from a reference and allocated according to
the principles outlined above falls outside one of the end levels, a reference
word from the other side of the kernel is used. This may happen, for
example, when the peak of the pdf is not in the central part of the level
distribution. The following example illustrates the principle, where we
assume that the peak of the pdf is located at level 5.
CA 022380l5 l998-05-l5
W0 97/20395 12 PCT/SE96/015S5
Step 1 Step 2 Step 3 Step 4
Level Code Code Code CodeDistance d1
0 0001 +1+4=6
1 100 1001 +6+5=12
2 010 010 0105+2+2=9
3 001 001 -->0013+1+3=7
4 --> 011 011 0111 ~1+2=4
111 111 111 1111 +1+2=4
6 101 --> 101 1013~1+5=9
7 110 110 110~;+6+2=13
7.2 More general pdf (Basng-2 code).
This technique may be used when the pdf has a more general shape and the
design steps are as follows. Here we illustrate the method by a 4 bit code
(n = 4) .
7.2.1) Initialise the code tsble.
7.2.1.a) Pick a (n-1) bit code word, for example 111, denoted kernel, and put
it on the level position that corresponds to the peak of the level pdf, say level
8.
Level Code Word
8 111
7.2.1.b) Insert a maximum of ~n-1) new code words with Hamming distance
one from the kernel and put them on the distances d = ld1, d2, ... dk ~ units
from the kernel, in our example we choose dt = 1, d2 = 3 and d3 = 5 and
we get, -
CA 022380l5 l998-05-l5
WO 97/20395 PCT/SE96/015~5
13
Level Code Word
-- 3 011
__ 5 101
d3 6
d2 ~~~~i~ 7 110
-- 8 111 (kernel~
~0
7.2.Z) Continue to build the table.
7.2.2.a) The code table is built from the kernel and upwards and the code
word associated with the distance d1 is used as the 1 :st reference, i.e. 110.
(The index in the distance measure is taken as the order in which the
references are processed).
Changing, the bits in the 1 :st reference and packing the new words as close
as possible to the kernel we get
Level Code Word
3 011
4 100
101
6 010
7 --> 110
8 111
Next we use the code word associated with d2, 101, as a reference,
3 0 changing the bits and obtain
CA 02238015 1998-05-15
W O 97/20395 14 PCT/S~96101555
Level Code Word
2 001
3 011
4 100
5 -> 101
6 010
7 110
8 111
Next reference corresponding to d3, 01 1, does not give any new code
word, and all the references have now been used.
~5
2.2.2~b) With the code word next to the kernel as a reference, 1 10, chan~e
the bits and fili up the table with new code words in positions as close as
possible to the kernel. In this case 1 10 does not give any new code word
and so continue with the next code word counted from the kernel, namely
010.
Level Code Word
000
2 001
3 011
4 100
101
6 --~ 010
7 110
8 111
and we have all 8 code words.
CA 0223801~ 1998-0~
WO 97/20395 15 PCT/SE96/01555
7.2.2.c) To obtain the 16 possible code words for the 4 bit code we take
the mirror picture of the 8 code words below the 8:th word (or above the
1 :st word) and put a 1 (or 0) at the leftmost position (or rightmost position
or any position) of the 8 original words and a 0 (or 1 ) at the same bit
position in the reflected 8 words,.i.e. one implementation gives
Level Code WordDistance d1
1 OQ0 24
2 1001 18
3 1011 18
4 1100 16
1101 14
6 1010 12
7 1110 8
8 1111 10
9 0111 10
0110 8
11 0010 12
12 0101 14
13 0100 16
14 0011 18
0001 18
16 0000 24
The design method ensures a symmetrical distance distribution d1 ~m) and
d2(m) and it allows a flexibility to adapt the distance distribution to the
actual pdf of the level in such a way that a small distance is allocated to the
peak(s) of the pdf, thereby making the mean error distance per bit ~l and
the squared distance per bit ~2 small.
, 30
Forbidden code words are removed from the table.
CA 022380l5 l998-05-l5
WO 97/20395 16 PCT/SE96/01555
To illustrate the flexibility of the Baang-2 code methodolo~y, we generate 2
different 4 bit code tables based on the two initialisation vectors
d" = [1 3 7l and db = t1 2 3] and this time we show the metric d2(m~
~mse). The kernel is chosen to 111. See Table 3.
CA 022380l5 l998-05-l5
WO 97/20395 17 PCT/SE96/01555
Level Code d2lm) Code d2(m)
m da db
1 011 287 1 000 239
2 1000 190 1001 195
3 1001 130 1010 145
4 1010 103 1100 103
1101 63 1011 71
6 11 00 43 11 01 49
7 1110 20 1110 35
8 1111 60 1111 15
9 0111 60 0111 15
0110 20 0110 35
11 0100 43 0101 49
12 0101 63 0011 71
13 0010 103 0100 103
14 0001 130 0010 145
1Ei 0000 190 0001 195
16 001 1 287 0000 239
Table 3.
As a comparison a straigth code has d2~m) = 85 for each code word.
7.3 Variations of code tables.
The bit-columns of the code tables can be changed in any order without
changing the metric (distance~.
Ones can be exchanged by zeros and vice versa without changing the
metric .
CA 0223801~ 1998-0~
WO 97/20395 18 PCT/SE96/01555
Baang-~ code.
The Baang-1 code gives the minimum distance (or mse) to code words with
Hamming distance one, i.e. for code words with single bit errors, to the
kernel.
Alternative code words on each side of the kernel are designed in such a
way that the levels associated with the Hamming distance = 1 to the code
word considered are minimised.
The kernel has the least possible distance (or mse) and the distance
measure (or mse) increases further away from the kernel.
The Baang-1 code is particularly useful for representing information that has
a peak in its pdf.
Although the design method has been described for a short 3-bit code, for
the purpose of illustration, the same design principle is applicable for longer
codes. Furthermore, the maximum gain compared to a straight code
increases with the length of the code words.
Baang-2 code.
With this design method we have a possibility to adapt the error distances
to the peak(s) of the pdf in such a way that small error distances are
allocated to the peak(s) of the pdf. The way to control this allocation is by
means of the initialisation process i.e. how we set the reference code words
related to the kernel - the distances d1, d2, d3, ... dk, where
0 < k < n-1 and where each d-component takes on distinct integer values
in the interval [1, 2(n~ 1]. The d-values are put at positions where the pdf
has high values.
CA 0223801~ 1998-OS-lS
W O 97/20395 19 PCT/SE96/01555
Columns in the code table can be reordered in any order without changing
the distance measures. Ones can be replaced by zeros and vice versa
without changing the distance measures. The initialisation process can, of
course, also generate new code words downwards (instead of upwards) and
the code table can be generated in an apparent way based on the steps
described above ( a symmetry principle).
The arrangement in accordance with the invention comprises means for
allocating a new code word to the other side of the kernel in cases where
the end of the code table has been reached on the side where said code
word should be allocated according to previous steps. The arrangement also
comprises means to stop new code word generation when all 2" code
words have been generated and means for removing not allowed code
word(s), which with a suitable choice of the kernel as previously described,
is (are) allocated towards the end(s) of the code table. A number of
variations of the above mentioned embodiments are of course possible
Bit-columns in the code table can e.g. be reordered in any order without
changing the distance measures. Binary "ones" can be replaced by "zeros"
and vice versa without changing the distance measures.
