Coding and decoding methods and devices and equipment using them

• US 6,393,065 B1
• Filed: 08/28/1998
• Issued: 05/21/2002
• Est. Priority Date: 08/29/1997
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.), Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Le Dantec, Claude, Piret, Philippe
• Primary Examiner(s): VO, DON NGUYEN
• Application Number:
  US09/141,589
• Time in Patent Office: 1,362 Days
• Field of Search: 375/261, 375/259, 714/6, 714/784, 341/51, 341/52, 341/94, 341/106, 341/107
• US Class Current: 375/261
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/251 with block coding
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

A coding device that supplied code words, the symbols of which are capable of modulating a physical quantity on a transmission channel making use of symbols of a first alphabet. The decoding of these words uses symbols of a second alphabet containing the first alphabet, the cardinal of the second alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet. The coding device has an input of the “primary” symbols belonging to the first alphabet, a processor which determines redundant symbols capable of allowing decoding of the code words formed from primary symbols and redundant symbols, by a decoder working on the second alphabet, and solves a system of equations expressing the constraints to be met so that the redundant symbols are in the first alphabet, and an output of the symbols of the code words.

Claims

1. Coding device (10) supplying code words, the symbols of which are capable of modulating a physical quantity on a transmission channel making use of symbols of a first alphabet, the decoding of these ode words using symbols of a second alphabet containing the first alphabet, the cardinal of the alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet, a device characterized in that it has:

an input (103,111) of “

primary symbols belonging to the first alphabet;

processing means (104, 105, 106) adapted to determined redundant symbols capable of allowing decoding of the code words formed primary symbols and redundant symbols, by a decoder (20) working on the second alphabet by solving a system of equations expressing the constraints to be met so that said redundant symbols are in the first alphabet.

an output (107) of the symbols of the code words.

3. Coding device according to either one of claims 1 or 2, chracterised in that the processing means (104, 105, 106) are adapted to solve the system of equations by successively loving sub-systems of equations each having a number of unknown strictly less than the number of unknowns of the complete system of equations.

4. Coding device according to either claim 1 or 2, characterised in that the processing means (104, 105, 106) are adapted to use the second alphabet which, provided with an operation, constitutes a group, and the first alphabet which, provided with the same operation, constitutes a subgroup of the second alphabet.

5. Coding device according to claim 4, characterised in that the processing means (104, 105, 106) are adapted to use the second alphabet which, provided with two operations, constitutes a Galois field, and the first alphabet which, provided with the same two operations, does not constitute a Galois sub-field of the second alphabet.

6. Coding device according to either claim 1 or 2, characterised in that the processing means (104, 105, 106) are adapted to use a first alphabet which has 64 symbols.

7. Coding device according to either claim 1 or 2, characterised in that the processing means (104, 105, 106) are adapted to use a second alphabet which has 256 symbols.

8. Coding device according to either claim 1 or 2, characterised in that the processing means (104, 105, 106) are adapted to use a second alphabet composed of binary sequences and a first alphabet composed of binary sequences from the second alphabet, of which certain units of binary information have a predetermined value.

9. Coding device according to either claim 1 or 2, characterised in that the processing means (104, 105, 106) are adapted to supply code words which belong to a Reed-Solomon code.

10. Coding device according to either claim 1 or 2, characterised in that the processing means (104, 105, 106) are adapted to use matrix calculations.

11. Coding device according to either claim 1 or 2, characterised in that it has a modulator (109) adapted to perform a quadrature amplitude modulation.

12. Sending System, characterised in that it has a coding device (10) according to either claim 1 or 2, and means of sending (109, 110) a signal modulating the physical quantity representing symbols of the code words generated by the said coding device.

13. Computer, characterised in that it has a coding device according to either claim 1 or 2.

14. Device for capturing physical quantities having a sensor, characterised in that it has a coding device according to either claim 1 or 2.

2. Coding device (10) supplying code words, the symbols of which are capable of modulating a physical quantity on a transmission channel making use of symbols of a first alphabet, the decoding of these code words using symbols of a second alphabet containing the first alphabet, the cardinal A₂ of the second alphabet being strictly greater than the cardinal A₁ of the first alphabet and not being an integer power of A₁, both A₁ and A₂ being powers of 2, a device characterised in that it has:

an input (103, 111) of “

primary”

symbols belonging to the first alphabet;

processing means (104, 105, 106) adapted to replace a part of the primary symbols by symbols representative of these primary symbols, said part containing a number of bits equal to

15. Coding method supplying code words, the symbols of which are capable of modulating a physical quantity on a transmission channel making use of symbols of a first alphabet, the decoding of these code words using symbols of a second alphabet containing the first alphabet, the cardinal of the second alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet, a method characterised in that it has:

a step of inputting (501) “

primary”

symbols belonging to the first alphabet;

a step of determining (503 to 507) redundant symbols capable of allowing decoding of the code words formed from primary symbols and redundant symbols, by a decoder working on a second alphabet including the first alphabet and symbols not belonging to the first alphabet, having an operation of solving (504, 505, 506) a system of equations expressing the constraints to be met so that the redundant symbols are in the first alphabet;

a step of outputting (508) the symbols of the code words.

17. Coding method according to either one of claims 15 or 16, characterised in that, during the operation of solving the said system of equations, steps (504, 505, 506) are successively performed for solving sub-systems of equations each having a number of unknowns strictly less than the number of unknowns of the complete system of equations.

18. Coding method according to either claim 15 or 16, characterised in that it uses the second alphabet which, provided with an operation, constitutes a group, and the first alphabet which, provided with the same operation, constitutes a sub-group of the second alphabet.

19. Coding method according to claim 18, characterised in that it uses the second alphabet which, provided with two operations, constitutes a Galois field, and the first alphabet which, provided with the same two operations, does not constitute a Galois sub-field of the second alphabet.

20. Coding method according to either claim 15 or 16, characterised in that it uses a first alphabet which has 64 symbols.

21. Coding method according to either claim 15 or 16, characterised in that it uses a second alphabet which has 256 symbols.

22. Coding method according to either claim 15 or 16, characterised in that the second alphabet is composed of binary sequences and the first alphabet is composed of binary sequences from the second alphabet, of which certain units of binary information have a predetermined value.

23. Coding method according to either claim 15 or 16, characterised in that the code words belong to a Reed-Solomon code.

24. Coding method according to either claim 15 or 16, characterised in that, during the determination operation (504, 505, 506), matrix calculations are used.

35. Information storage means which can be read by a computer or a microprocessor, storing instructions of a computer program characterised in that it enables the method according to either claim 15 or 16 to be implemented.

16. Coding method supplying code words, the symbols of which are capable of modulating a physical quantity on a transmission channel making use of symbols of a first alphabet, the decoding of these code words using symbols of a second alphabet containing the first alphabet, the cardinal A₂ of the second alphabet being strictly greater than the cardinal A₁ of the first alphabet and not being an integer power of A₁, both A₁ and A₂ being powers of 2, a method characterised in that it has;

an step of inputting (501) “

primary”

symbols belonging to the first alphabet;

a step (503 to 507) of replacing a part of the primary symbols by symbols representative of these primary symbols, the replaced part containing a number of bits equal to

25. Decoding device, characterised in that it has:

an input (209, 210) of symbols of a first alphabet used on a transmission channel, and

a decoding means (211) adapted to decode symbols of a second alphabet containing the first alphabet, the cardinal of the second alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet,

the symbols of the second alphabet being, at the input of the decoding means, composed of the juxtaposition of symbols of the first alphabet and predetermined symbols.

26. Decoding device according to claim 25, characterised in that the transmission channel is adapted to use a first alphabet which has 64 symbols.

27. Decoding device according to claim 25, characterised in that the decoding means (211) is adapted to use a second alphabet which has 256 symbols.

28. Decoding device according to claim 25, characterised in that the decoding means (211) is adapted to decode words of a Reed-Solomon code.

29. Decoding device according to claim 25, characterised in that it has a demodulator (210) adapted to perform a quadrature amplitude demodulation of signals transmitted on the transmission channel.

30. Receiving system, characterised in that it has a decoding device according to claim 25 and a means of receiving (209, 210) signals from the transmission channel.

31. Decoding method, characterised in that it has:

a step of inputting symbols of a first alphabet used on a transmission channel, and

a decoding step, during which symbols of a second alphabet containing the first alphabet are decoded, the cardinal of the second alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet,

the symbols of the second alphabet decoded during the decoding step being composed of the juxtaposition of symbols of the first alphabet and predetermined symbols.

32. Decoding method according to claim 31, characterised in that, during the inputting step, a first alphabet which has 64 symbols is used.

33. Decoding method according to claim 31, characterised in that, during the decoding step, a second alphabet which has 256 symbols is used.

34. Decoding method according to claim 31, characterised in that, during the decoding step, words of a Reed-Solomon code are decoded.

36. Information storage means which can be read by a computer or a microprocessor, storing instructions of computer program characterised in that it enables the method according to claim 31 to be implemented.