Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-07-14
2003-04-01
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S780000, C714S758000
Reexamination Certificate
active
06543021
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention concerns a method and a device for coding and transmission using a sub-code of a product code.
The object of the present invention is to combat errors appearing during the transmission of information, notably within the context of wireless transmission. This is because the transmitted signals, notably those of an electrical nature, are disrupted by noise.
2. Description of the Related Art
A message is defined as being a digital sequence.
One solution consists of making the message redundant, that is to say adding redundancy into the message: in other words, in addition to the symbols representing the information, symbols are transmitted which are functions of the said symbols representing the information.
A device which produces a sequence in an alphabet is called a coder.
A set of sequences produced by the coder is called a code.
To specify a code, or to specify the way of calculating the redundancy to be appended to an item of information, use is often made of matrices. For example, if it is wished to append redundant symbols (v
4
, v
5
, v
6
) (the number of redundant symbols is three in this example) to k binary information symbols (v
0
, v
1
, v
2
, v
3
) (the number of binary information symbols is denoted k and is equal to four in this example), in order to form the word v=(v
0
, . . . , v
6
) of length n (n is equal to seven in this example), a matrix H with n columns and n−k rows (three in this example) in the alphabet {0, 1} is produced, such that for example
H
=
&LeftBracketingBar;
1
1
1
0
1
0
0
0
1
1
1
0
1
0
1
1
0
1
0
0
1
&RightBracketingBar;
,
and the binary word v of length seven is made to satisfy the equation v
i
*H
r
=0, where “*” designates the matrix product, where H
r
designates the transposed matrix of the matrix H and where the additions are performed modulo 2: the word v is then said to be orthogonal to the matrix H. In this example, the redundant symbols v
4
, v
5
and v
6
are therefore calculated as follows;
v
4
=v
0
+v
1
+v
2
v
5
=v
1
+v
2
+v
3
v
6
=v
0
+v
1
+v
3
.
The parameter n is called the code length and the parameter k, which is always strictly less than the parameter n, is called the code dimension. The matrix H used in this way is called the parity control matrix or parity matrix.
It is well known that this coding method makes it possible to correct one error: if, after having sent the binary word v on a noisy channel, the binary word r=(r
0
, . . . , r
6
) is received where, for at most one index i, one of the symbols r
i
is different from the symbol v
i
, the correction of this error is possible (see Peterson and Weldon, “
Error-Correcting Codes
” MIT Press). More generally, for a fairly large parameter n, more efficient codes can be obtained by increasing the value of the parameter n−k. Such codes make it possible to correct more than one erroneously received symbol. A tool of choice in the implementation of such codes, referred to as linear codes, is then the syndrome s=r*H
r
corresponding to the received word r (cf. the Peterson and Weldon reference cited above).
With the aim of improving the transmission performance by means of a coding allowing error correction, without increasing the complexity of its implementation “too much”, the product code idea is resorted to: a message to be transmitted which has k*k symbols constituting the information is considered. These symbols are disposed at the top left in a square table of dimension n*n: the first k places of the first k rows of the table have thus been filled, counting the places in the rows from the left and counting the rows in the table from the top. The other n−k places in each row of the table are filled by redundant symbols which depend only on the first k symbols in the row in question: the first k rows of the table or in other words the first k places of each column have thus been entirely filled, counting the places in the columns from the top. The other n−k places in each column of the table are filled by redundant symbols which depend only on the first k symbols in the column in question: the table has thus been entirely filled.
In order to decode a message which comes in the form of a product code, a start can be made by decoding the rows, and the corrections made, if necessary. Then, with the corrected data, the columns are decoded and the corrections made. The method can thus be iterated.
A hard iterative decoding method based on hard demodulation is considered in the article “Diagonals of 2D-Abelian codes” by J. Lacan, published in the proceedings of the 1998 Information Theory Workshop, pp 110-111.
Another improvement of the transmission performance is possible by resorting to a so-called soft decision demodulation method. With this method, a received symbol, denoted rand corresponding to a symbol sent in the alphabet {0, 1}, is no longer interpreted as an element of this alphabet {0, 1}. The information
, provided by the symbol r and which can be used by a decoder, is then expressed by the formula
=log[f(r)] where log designates the logarithm of its argument in a base strictly greater than 1, and where f(r) is the ratio between the likelihood of receiving a value close to r when 1 is sent and that of receiving a value close to r when 0 is sent. This logarithm is called the log-likelihood-ratio (l.l.r.).
When such a soft decision can be made, the decoding of product codes proves to be particularly efficient (see on this subject: J. Hagenauer, E. Offer and L Papke, “
Iterative decoding of binary block and convolutional codes”
, IEEE Transactions on Theory, vol. 42, pp 429-445, March 1996 and R. Pyndiah, A. Glavieux, A. Picart and S. Jacq, “
Near optimum decoding of product codes
”, Proceedings IEEE Globecom Conference, pp 339-343, San Francisco, November 1994). The theoretical ideas at the basis of these articles date back to the book by R. G. Gallager, “
Low
-
density parity
-
check codes
”, published by MIT Press in 1963, but the above articles succeed in specifying how to implement these theoretical bases efficiently.
In practice, the letters of the alphabet {0, 1} are transmitted on the channel by two different electrical signals and identified with the numbers +1 (for the letter 0) and −1 (for the letter 1). As long as the electrical signals chosen in this way are “reasonable” and the noise affecting the channel not too different from the conventional Additive White Gaussian Noise, better known by the initials AWGN, the situation of such a channel is well known and commonly studied.
To illustrate the usage of the ideas introduced above, this particular simple example is considered. The control matrix H=[1 1 1] defines a code (n=3, k=2) in the alphabet {0, 1}. By applying the construction mentioned above of product code of this code by itself, four binary symbols v
0,0
v
0,1
, v
1,0
and v
1,1
, can be used to construct the binary word v of length 9 represented by this particular 3*3 matrix:
v
=
v
0
,
0
v
0
,
1
v
0
,
2
v
1
,
0
v
1
,
1
v
1
,
2
v
2
,
0
v
2
,
1
v
2
,
2
,
where the symbols v
2,0
, v
2,1
, v
2,2
, v
0,2
and v
1,2
have been calculated so that the three rows and the three columns of the word v are orthogonal to the matrix H.
By virtue of the parity relationships imposed by the matrix H on these symbols v
i,j
, it may be concluded that v
1,1
(for example) satisfies the equations:
v
1,1
=v
0,1
+v
1,2
(1)
v
1,1
=v
0,1
+v
2,1
(2)
where the additions are performed modulo 2. After transmission of a symbol v
ij
on the channel, a calculation can be performed, for the received symbol r
ij
which corresponds to it, of the log-likelihood-ratio
ij
=[log f(r
ij
)], and the matrix
of these values
i,j
can be constructed:
𝒥
=
𝒥
0
,
0
𝒥
0
,
1
𝒥
0
,
2
𝒥
1
,
0
𝒥
1
,
1
𝒥
1
,
2
&
Britt Cynthia
Canon Kabushiki Kaisha
De'cady Albert
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Method and device for coding and transmission using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for coding and transmission using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for coding and transmission using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3030680