Decoding apparatus and decoding method

• US 20010034871A1
• Filed: 03/26/2001
• Published: 10/25/2001
• Est. Priority Date: 03/29/2000
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Takeda, Daisuke, Mukai, Manabu
• Granted Patent: US 6,912,685 B2
• Time in Patent Office: Days
• US Class Current: 714/781
• CPC Class Codes: H03M 13/136 Reed-Muller [RM] codes
• CPC Class Codes: H03M 13/451 using a set of candidate code words, e.g. ordered statistics decoding [OSD]

Abstract

Decoding apparatus comprises EX-OR circuit exclusive ORing the Reed-Muller code and exclusive Ored value of mask symbol candidate pattern and the information data corresponding to the pattern, first decoder calculating checksum of the EX-OR circuit output and majority-judging the checksum to decode a part of the second portion of the information data, second decoder exclusive ORing the EX-OR circuit output and a product of the part of the second portion and the orthogonal codes and majority-judging the exclusive OR result to decode a remaining part of the second portion, Reed-Muller encoder encoding the information data, and minimum detector detecting the minimum of Euclidean distance between an output from the Reed-Muller encoder and the Reed-Muller code supplied to the arithmetic operation unit while a plurality of candidate patterns of the mask symbols are supplied to the arithmetic operation unit.

Claims

1. An apparatus for decoding Reed-Muller code in which information data is encoded by using mask symbols and orthogonal codes, the information data including a first portion and a second portion, the apparatus comprising:

an arithmetic operation unit configured to calculate a first exclusive OR of the Reed-Muller code and an exclusive ORed value of a candidate pattern of the mask symbols and the information data corresponding to the candidate pattern;

a first decoder configured to calculate a checksum of the first exclusive OR and majority-decide the checksum to decode a part of the second portion of the information data corresponding to the orthogonal codes;

a second decoder configured to calculate a second exclusive OR of the first exclusive OR and a product of the part of the second portion of the information data and the orthogonal codes and majority-decide the second exclusive OR to decode a remaining part of the second portion of the information data corresponding to the orthogonal codes;

a Reed-Muller encoder configured to Reed-Muller encode the second portion of the information data output from the first decoder and the second decoder and the first portion of the information data;

a minimum distance detector configured to detect the minimum of a Euclidean distance between an output from the Reed-Muller encoder and the Reed-Muller code supplied to the arithmetic operation unit while a plurality of candidate patterns of the mask symbols are supplied to the arithmetic operation unit,

whereby the first portion of the information data is decoded based on the mask symbols corresponding to the minimum of the Euclidean distance.

2. The apparatus according to

claim 1

, further comprising a memory configured to store a plurality of exclusive ORed value of a plurality of candidate patterns of the mask symbols and a plurality of information data corresponding to the candidate patterns, and wherein the arithmetic operation unit calculates the first exclusive OR of the Reed-Muller codes and each of the plurality of exclusive ORed values stored in the memory.

3. The apparatus according to

claim 1

, further comprising a hard decision unit configured to hard-decide the Reed-Muller code supplied to the arithmetic operation unit.

4. The apparatus according to

claim 1

, wherein the first decoder comprises:

a memory configured to store the first exclusive OR output from the arithmetic operation unit;

a checksum calculator configured to read bit data from the memory and calculate a plurality of exclusive ORs of a plurality of sets of the read bit data to obtain a plurality of checksums;

a selector configured to select some of the plurality of checksums based on a type of the Reed-Muller code;

an accumulator configured to accumulate the selected checksums; and

a hard decision unit configured to hard-decide an output from the accumulator.

5. A method of decoding Reed-Muller code in which information data is encoded by using mask symbols and orthogonal codes, the information data including a first portion and a second portion, the method comprising:

calculating a first exclusive OR of the Reed-Muller code and an exclusive ORed value of a candidate pattern of the mask symbols and the information data corresponding to the candidate pattern;

calculating a checksum of the first exclusive OR and majority-judging the checksum to decode a part of the second portion of the information data corresponding to the orthogonal codes;

calculating a second exclusive OR of the first exclusive OR and a product of the part of the second portion of the information data and the orthogonal codes and majority-judging the second exclusive OR to decode a remaining part of the second portion of the information data corresponding to the orthogonal codes;

Reed-Muller encoding the decoded second portion of the information data and the first portion of the information data; and

detecting the minimum of a Euclidean distance between the Reed-Muller encoded data and an input Reed-Muller code while a plurality of first exclusive ORs are calculated, whereby the first portion of the information data is decoded based on the mask symbols corresponding to the minimum of the Euclidean distance.

6. An apparatus for decoding Reed-Muller code in which information data is encoded by using mask symbols and orthogonal codes, the information data including a first portion and a second portion, the apparatus comprising:

a first arithmetic operation unit configured to calculate an exclusive OR of the Reed-Muller code and an exclusive ORed value of a candidate pattern of the mask symbols and the information data corresponding to the candidate pattern;

a decoder configured to calculate a checksum of the exclusive OR and majority-decide the checksum to decode a part of the second portion of the information data corresponding to the orthogonal codes;

a second arithmetic operation unit configured to calculate a first accumulation result of each bit of a product of an output from the decoder and the orthogonal codes and a second accumulation result of each inverted bit of a product of the output from the decoder and the orthogonal codes and detect one of the first accumulation result and the second accumulation result which corresponds to a smaller Euclidean distance between the Reed-Muller code input to the first arithmetic operation unit and encoded data of decoded data;

a minimum detector configured to detect the minimum of an output from the second arithmetic operation unit while a plurality of candidate patterns of the mask symbols are supplied to the first arithmetic operation unit,

whereby the first portion of the information data is decoded based on the mask symbols corresponding to the minimum of the output from the second arithmetic operation unit.

7. The apparatus according to

claim 6

, further comprising a memory configured to store a plurality of exclusive ORed value of a plurality of candidate patterns of the mask symbols and a plurality of information data corresponding to the candidate patterns, and wherein the first arithmetic operation unit calculates the exclusive OR of the Reed-Muller codes and each of the plurality of exclusive ORed values stored in the memory.

8. The apparatus according to

claim 6

, further comprising a hard decision unit configured to hard-decide the Reed-Muller code supplied to the first arithmetic operation unit.

9. The apparatus according to

claim 6

, wherein the decoder comprises:

a memory configured to store the exclusive OR output from the first arithmetic operation unit;

a checksum calculator configured to read bit data from the memory and calculate a plurality of exclusive ORs of a plurality of sets of the read bit data to obtain a plurality of checksums;

a selector configured to select some of the plurality of checksums based on a type of the Reed-Muller code;

an accumulator configured to accumulate the selected checksums; and

a hard decision unit configured to hard-decide an output from the accumulator.

10. A method of decoding Reed-Muller code in which information data is encoded by using mask symbols and orthogonal codes, the information data including a first portion and a second portion, the method comprising:

calculating an exclusive OR of the Reed-Muller code and an exclusive ORed value of a candidate pattern of the mask symbols and the information data corresponding to the candidate pattern;

calculating a checksum of the exclusive OR and majority-decide the checksum to decode a part of the second portion of the information data corresponding to the orthogonal codes;

calculating a first accumulation result of each bit of a product of decoded data and the orthogonal codes and a second accumulation result of each inverted bit of a product of the decoded data and the orthogonal codes and detect one of the first accumulation result and the second accumulation result which corresponds to a smaller Euclidean distance between the input Reed-Muller code and encoded data of the decoded data;

detecting the minimum of one of the first accumulation result and the second accumulation result which has a smaller Euclidean distance between the input Reed-Muller code and encoded data of the decoded data while calculating the exclusive OR of the Reed-Muller code and an exclusive ORed value of each of a plurality of candidate patterns of the mask symbols and the information data corresponding to the candidate pattern,

whereby the first portion of the information data is decoded based on the mask symbols corresponding to the minimum of one of the first accumulation result and the second accumulation result which has a smaller Euclidean distance between the input Reed-Muller code and encoded data of the decoded data.

11. An apparatus for decoding Reed-Muller code in which information data is encoded by using mask symbols and orthogonal codes, the information data including a first portion and a second portion, the apparatus comprising:

an arithmetic operation unit configured to calculate a first product of the Reed-Muller code and an exclusive ORed value of a candidate pattern of the mask symbols and the information data corresponding to the candidate pattern;

a first decoder configured to calculate a checksum of the first product and majority-decide the checksum to decode a part of the second portion of the information data corresponding to the orthogonal codes;

a second decoder configured to calculate a second product of the first product and a product of the part of the second portion of the information data and the orthogonal codes and majority-decides the second product to decode a remaining part of the second portion of the information data corresponding to the orthogonal codes;

a Reed-Muller encoder configured to Reed-Muller encode the second portion of the information data output from the first decoder and the second decoder and the first portion of the information data;

a maximum correlation detector configured to detect the maximum of a correlation between an output from the Reed-Muller encoder and the Reed-Muller code supplied to the arithmetic operation unit while a plurality of candidate patterns of the mask symbols are supplied to the arithmetic operation unit,

whereby the first portion of the information data is decoded based on the mask symbols corresponding to the maximum of the correlation.

12. The apparatus according to

claim 11

, further comprising a memory configured to store a plurality of exclusive ORed value of a plurality of candidate patterns of the mask symbols and a plurality of information data corresponding to the candidate patterns, and wherein the arithmetic operation unit calculates the first product of the Reed-Muller code and each of the plurality of exclusive ORed values stored in the memory.

13. The apparatus according to

claim 11

, wherein the first decoder comprises:

a memory configured to store the first product;

a checksum calculator configured to read bit data from the memory and calculate a plurality of exclusive ORS of a plurality of sets of the read bit data to obtain a plurality of checksums;

a selector configured to select some of the plurality of checksums based on a type of the Reed-Muller code; and

an accumulator configured to accumulate the selected checksums.

14. A method of decoding Reed-Muller code in which information data is encoded by using mask symbols and orthogonal codes, the information data including a first portion and a second portion, the method comprising:

calculating a first product of the Reed-Muller code and an exclusive ORed value of a candidate pattern of the mask symbols and the information data corresponding to the candidate pattern;

calculating a checksum of the first product and majority-decide the checksum to decode a part of the second portion of the information data corresponding to the orthogonal codes;

calculating a second product of the first product and a product of the part of the second portion of the information data and the orthogonal codes and majority-decides the second product to decode a remaining part of the second portion of the information data corresponding to the orthogonal codes;

Reed-Muller encoding the second portion of the information data and the first portion of the information data;

detecting the maximum of a correlation between the Reed-Muller encoded data and an input Reed-Muller code while a plurality of first products are calculated, whereby the first portion of the information data is decoded based on the mask symbols corresponding to the maximum of the correlation.

15. An apparatus for decoding Reed-Muller code in which information data is encoded by using mask symbols and orthogonal codes, the information data including a first portion and a second portion, the apparatus comprising:

a first arithmetic operation unit configured to calculate a first product of the Reed-Muller code and an exclusive ORed value of a candidate pattern of the mask symbols and the information data corresponding to the candidate pattern;

a decoder configured to calculate a checksum of the first product and majority-decide the checksum to decode a part of the second portion of the information data corresponding to the orthogonal codes;

a second arithmetic operation unit configured to calculate a first accumulation result of each bit of a product of an output from the decoder and the orthogonal codes and a second accumulation result of each inverted bit of a product of the output from the decoder and the orthogonal codes and detect a larger one of the first accumulation result and the second accumulation result;

a maximum detector configured to detect the maximum of an output from the second arithmetic operation unit while a plurality of candidate patterns of the mask symbols are supplied to the first arithmetic operation unit,

whereby the first portion of the information data is decoded based on the mask symbols corresponding to the maximum of the output from the second arithmetic operation unit.

16. The apparatus according to

claim 15

, further comprising a memory configured to store a plurality of exclusive ORed value of a plurality of candidate patterns of the mask symbols and a plurality of information data corresponding to the candidate patterns, and wherein the first arithmetic operation unit calculates the first product of the Reed-Muller code and each of the plurality of exclusive ORed values stored in the memory.

17. The apparatus according to

claim 15

, wherein the decoder comprises:

a memory configured to store the first product;

a checksum calculator configured to read bit data from the memory and calculate a plurality of exclusive ORs of a plurality of sets of the read bit data to obtain a plurality of checksums;

a selector configured to select some of the plurality of checksums based on a type of the Reed-Muller code; and

an accumulator configured to accumulate the selected checksums.

18. A method of decoding Reed-Muller code in which information data is encoded by using mask symbols and orthogonal codes, the information data including a first portion and a second portion, the method comprising:

calculating a first product of the Reed-Muller code and an exclusive ORed value of a candidate pattern of the mask symbols and the information data corresponding to the candidate pattern;

calculating a checksum of the first product and majority-decide the checksum to decode a part of the second portion of the information data corresponding to the orthogonal codes;

calculating a first accumulation result of each bit of a product of decoded data and the orthogonal codes and a second accumulation result of each inverted bit of a product of the decoded data and the orthogonal codes and detect a larger one of the first accumulation result and the second accumulation result;

detecting the maximum of the first accumulation result and the second accumulation result while calculating the first product of the Reed-Muller code and an exclusive ORed value of each of a plurality of candidate patterns of the mask symbols and the information data corresponding to the candidate pattern,

whereby the first portion of the information data is decoded based on the mask symbols corresponding to the maximum of the first accumulation result and the second accumulation result.