Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
1999-12-16
2002-07-16
Baker, Stephen M. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S778000
Reexamination Certificate
active
06421806
ABSTRACT:
The present invention relates to an information transfer device and method, an information receiving device and method and network stations using them.
8-state amplitude modulation (known by the name “8-AM”) can be described as follows. In order to transmit information, an alphabet
A={−7, −5,−3,−1,1,3,5,7}
containing eight numbers, referred to as elementary signals, is available. At each instant r.T, with r=0, 1, 2, . . . , a multiple of an elementary duration T, an information source selects a number a from the alphabet A and transmits this number a to a modulator. This modulator produces, between the instants r.T and (r+1).T, the electrical signal a. cos(2.&pgr;.f.t) (or, more precisely, a signal of amplitude proportional to a. cos(2.&pgr;.f.t)), where t is the time and f is the frequency of the carrier.
A received signal is often modified, for example by noise. This means that the received signal corresponding to a transmitted signal a. cos(2.&pgr;.f.t) (a being in the alphabet A) will be measured and evaluated as corresponding to the transmission of b. cos(2.&pgr;.f.t), a formula in which b may be different from a and is moreover not necessarily an element of A.
Sometimes, the noise level or modification, during a period T, are sufficiently high to make b. cos(2.&pgr;.f.t) closer to a*. cos(2.&pgr;.f.t) with a* in A, and a* different from a, than to any other transmittable signal, including a. cos(2.&pgr;.f.t). In this case, the decision rule is to estimate that a* was transmitted and an estimation error appears. It can be demonstrated that, with Additive White Gaussian Noise conditions, the probability of such an estimation error depends greatly on the amount (a-a*)
2
.T, and, the smaller the said amount, the higher this probability will be.
In particular, the probability of estimating a*=−7 when a=7 was transmitted is very low and the probability of estimating a*=3 when a=1 was transmitted is higher.
Furthermore, it is wished to have easy access to the information while receiving the noisy message. This property is referred to as an easy decoding method.
These same reasonings are found again for other amplitude modulation methods, such as 16-AM modulation (16-state amplitude modulation), for quadrature amplitude modulation methods, such as 64-QAM modulation (64-state quadrature amplitude modulation) and for phase modulation methods such as 8-PSK modulation (8-state phase modulation).
Let, for example, information transmission by means of 8-state amplitude modulated (“8-AM”) signals or 64-state quadrature amplitude modulated (“64-QAM”) signals be considered.
In the case of 8-AM modulation, the eight possible signals are therefore eight amplitudes proportional to the eight numbers of the alphabet A={−7, −5, −3, −1, 1, 3, 5, 7}, and in the case of 64-QAM modulation, the sixty-four possible signals are the sixty-four amplitude pairs (a, b), where a and b are two amplitudes each being proportional to one of the eight numbers of the alphabet A. A sequence of length n in the 64-QAM modulation alphabet can therefore be viewed as a sequence of length 2n in the 8-AM alphabet and everything which is said concerning coding adapted to 8-AM modulation can therefore easily be adapted to 64-QAM modulation.
When these signals are transmitted on a channel, for example a channel with Additive White Gaussian Noise (“AWGN”), the probability that the received signal is estimated as being equal to a
2
when the signal sent is a
1
depends, in effect, on the actual values of a
1
and a
2
.
Many methods used in practice do not, however, take these probabilities into account. These are designed to correct a certain number of erroneous received symbols, but their corrective capability is not expressed in terms of total amplitude of the error. In other words, they take into account only the Hamming distance between the received word and the code words, to the detriment of any other distance measurement, like for example the Lee distance.
Of course, efforts are sometimes made to take into account the amplitude of the error in the decoder but most often in the case of soft decoding, which makes the decoding expensive, or in the case of a channel whose input alphabet has at most four letters. On this subject, the article by Hammons, Kumar, Calderbank, Sloane and Solé entitled “The Z
4
- linearity of Kerdock, Preparata, Goethals and related codes”, IEEE Trans. On Inform. Theory, IT-40, pages 301 to 319, published in March 1994, should be consulted.
The present invention is concerned with a method of algebraic decoding of certain codes in the alphabet A, based on a judicious labelling of the elements of this alphabet by the integers 0, 1, . . . , 7, using a hard estimation of the received symbols and a notion of distance between words which is close to the Lee distance. On the subject of Hamming and Lee distances, the book by E. Berlekamp “
Algebraic Coding Theory
” published by McGraw-Hill in 1968 should be consulted. Simultaneously, specific coding schemes which produce good codes which can be decoded by this method will be described.
The invention aims to propose a coding method and device and, correlatively, a decoding method and device, which make it possible to recover the transmitted information, in the presence of noise.
An alphabet will be referred to as “numerical” if its symbols are real numbers or complex numbers viewed as pairs of real numbers. In an alphabet of real numbers, two symbols will be referred to as “adjacent” if the alphabet does not contain any other number which is both greater than one of these numbers and less than the other.
To this end, the present invention relates, according to a first aspect, to an information transfer method, characterised in that:
it uses:
an alphabet Z
2
t
={0, 1, 2, . . . 2
t
−1} having 2
t
elements, where t is at least equal to 3, and in which additions and multiplications are carried out modulo 2
t
, and
a cyclic code, possibly abbreviated, referred to as a “lifted Hamming code” obtained by lifting a binary Hamming code, and whose generator polynomial is the lifting into Z
2
t
of a generator polynomial of odd degree in {0, 1} of such a binary Hamming code; and
it includes:
an operation of coding the information by a sequence of words of the said lifted Hamming code,
a labelling operation, during which each letter of the alphabet Z
2
t
is used to label a letter of a numerical alphabet A, so that, for any pair of so-called “adjacent” symbols of A, the label of one of these symbols is the residue modulo 2
t
of the label of the other incremented by 1,
for each word of the said lifted Hamming code, an operation of transmitting signals with amplitudes proportional to the elements of A labelled by each of the symbols of the words of the said lifted Hamming code.
A labelling of the alphabet A satisfying the conditions described above (for any pair of so-called “adjacent” symbols of A, the label of one of these symbols is the residue modulo 2
t
of the label of the other incremented by 1) is referred to as “favourable”. A favourable labelling of a numerical alphabet is easily achieved by applying a principle of consecutiveness, of which here is an application:
letter of the alphabet A:
−7
−5
−3
−1
1
3
5
7
label
2
1
0
7
6
5
4
3
Correlatively, according to a second aspect, the present invention relates to a method of receiving a sequence of physical quantities representing information, characterised in that:
it uses:
a numerical alphabet A,
an alphabet Z
2
t
={0, 1, 2, . . . 2
t
−1} having 2
t
elements, where t is at least equal to 3, and in which additions and multiplications are carried out modulo 2
t
, and
a cyclic code, possibly abbreviated, referred to as a “lifted Hamming code” obtained by lifting a binary Hamming code, and whose generator polynomial is the lifting into Z
2
t
of a generator polynomial of odd degree in {0, 1} of suc
LandOfFree
Information transfer method and device, information... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Information transfer method and device, information..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Information transfer method and device, information... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2871244