Error correction coding utilizing numerical base conversion for modulation coding
View Patent ↗A method of encoding data includes representing the data as number(s) in a first base. The method further includes converting the number(s) into a number(s) in a second base. The resultant number in the second base can be viewed as data suitable for encoding using an ECC algorithm. After being ECC encoded, the data may be further modulation encoded. Modulation encoding may include transforming each symbol to a value that constrains run lengths of a binary value (e.g., zero). A decoding method and system checks a received data block for erroneous symbols, maps each received, encoded symbol to an associated ECC-encoded transform pair. The ECC encoded data may be decoded and corrected using the ECC and the locations of identified erroneous symbols. Finally, the corrected data sequence is converted from the second base back to the first base, from which the original data is retrieved.
1. A method of communicating data comprising steps of:
(a) representing data in a first base representation;
(b) converting the representation of the data in the first base to a representation of the data in a second base;
(c) error correction encoding the representation of data in the second base; and
(d) transforming coefficients of the error correction encoded representation of the data in the second base to obtain transformed encoded data meeting a specified constraint.
2. The method of claim 1 further comprising a step of:
(e) communicating the transformed encoded data via a medium.
3. The method of claim 2 wherein the medium is a data storage disc in a disc drive.
4. The method of claim 2 wherein the medium is a data storage tape in a tape drive.
5. The method of claim 2 wherein the medium is a transmission channel.
6. The method of claim 2 wherein the medium is an Internet.
7. The method of claim 2 further comprising steps of:
(f) retrieving the transformed encoded representation of the data from the medium, wherein the transformed encoded data as retrieved may be different from the transformed encoded data as communicated due to a disturbance in the medium.
8. The method of claim 7 further comprising steps of:
(g) transforming coefficients of the retrieved transformed encoded representation to obtain encoded data;
(h) error correction decoding the encoded data to obtain data represented in the second base; and
(i) converting the data represented in the second base to data represented in the first base.
9. The method of claim 8 wherein the second base is less than the first base and wherein the transforming step (g) comprises a step of:
(g)(i) subtracting the difference between the first base and the second base from the coefficients of the transformed encoded data.
10. The method of claim 8 further comprising steps of:
(j) performing an erasure-check upon the transformed encoded data to identify erasure data for the retrieved data; and
(k) correcting the retrieved data according to the erasure data.
11. The method of claim 10 wherein the performing step (j) comprises steps of:
(j)(i) identifying that one or more errors has occurred; and
(j)(ii) identifying the location of each identified error in the retrieved representation.
12. The method of claim 1 wherein the second base is less than the first base.
13. The method of claim 12 wherein the transforming step (d) comprises a step of:
(d)(i) mapping coefficients in the error correction encoded representation of the data in the second base to a symbol from a range of values defined by a function of the first and second bases.
14. The method of claim 13 wherein the range in the mapping step (d)(i) comprises:
a lower limit defined by the difference between the first base and the second base; and
an upper limit defined by the first base minus 1.
15. The method of claim 12 wherein transforming step (d) comprises a step of:
(d)(i) adding the difference between the first base and the second base to coefficients of the error correction encoded data.
16. The method of claim 1 wherein the data in the first base representation comprises coefficients in a first range, and wherein the transforming step (d) comprises a step of:
(d)(i) shifting the first range of the coefficients such that the transformed encoded data has a k-constraint that is a function of the first base and the second base.
17. The method of claim 1 wherein the transforming step (d) comprises a step of:
(d)(i) mapping each of the coefficients of the error correction encoded representation to a unique coefficient to ensure a predetermined k-constraint in the transformed encoded data.
18. A method of decoding data retrieved from a medium comprising steps of:
(a) error correction decoding the retrieved data; and
(b) converting symbols represented in a first base in the retrieved data to symbols represented in a second base.
19. The method of claim 18 further comprising steps of:
(c) transforming the retrieved data prior to error correction decoding.
20. The method of claim 19 wherein the first base is less than the second base and wherein the transforming step (c) comprises subtracting the difference between the first base and the second base from symbols in the retrieved data.
21. The method of claim 19 further comprising steps of:
(d) identifying erroneous symbols in the retrieved data, wherein the erroneous symbols are not among a set of allowed symbols.
22. The method of claim 21 further comprising steps of:
(e) initializing erasure information associated with the erroneous symbols, wherein the erasure information includes error location information used for error correction decoding.
23. The method of claim 22 wherein the first base is less than the second base and wherein the identifying steps (d) of identifying erroneous symbols comprises steps of:
(d)(i) identifying symbols having a value less than the difference between the first base and the second base.
24. The method of claim 18 wherein the first base is less than the second base.
25. A system for communicating data comprising: an encoder having a base converter module that converts input data from a first base to a second base and an error correction code encoding module that performs ECC encoding operations on the converted input data to create error correction encoded input data; and
a communicating module that communicates the error correction encoded input data to a medium.
26. The system of claim 25 wherein the encoder further comprises:
a first coefficient transformation module that maps symbols in the error correction encoded input data to a range of symbols chosen to meet a predetermined constraint.
27. The system of claim 26 wherein the second base is less than the first base and wherein the first coefficient transformation module further adds a value ‘r’ to each of the symbols in the error correction encoded input data, wherein the value ‘r’ is equal to (2 s −p a ), ‘s’ is a number of bits per symbol in the input data, 2 s is the first base, and p a is the second base.
28. The system of claim 27 , further comprising:
a retrieving module that retrieves the encoded data from the medium; and
a decoder having a base deconverter module that converts the retrieved encoded data from the second base to the first base.
29. The system of claim 28 wherein the decoder further comprises:
an erasure-check module that identifies symbols in the retrieved data in which an error has occurred.
30. The system of claim 28 wherein the second base is less than the first base and wherein the decoder further comprises a second coefficient transformation module that subtracts the value ‘r’ from each symbol in the retrieved data.
31. The system of claim 25 wherein the second base is less than the first base.
32. A disc drive comprising:
a communication module that writes encoded data to a disc in the disc drive; and
means for converting unencoded data in a first numerical base to error correction coded encoded data in a second numerical base, wherein the unencoded data and the error correction coded encoded data each comprise a plurality of symbols.
33. The disc drive of claim 32 wherein the means for converting comprises:
a base converter module that converts the unencoded data in the first base into transformed data in the second base;
an error-correction code module that encodes the transformed data in the second base with error correction code (ECC) parity data to derive the ECC encoded data; and
a coefficient transformation module that maps each symbol in the ECC encoded data to a unique symbol chosen from a predetermined set of symbols.
34. The disc drive of claim 33 wherein the second numerical base is less than the first numerical base and the base converter module comprises a downward base converter module.
35. The disc drive of claim 33 further comprising:
an erasure-check module that receives the encoded data from the disc as it may have been modified and identify one or more erroneous symbols in the encoded data;
an error-correction decode module that decodes the ECC encoded data represented in the second base; and
an upward base converter in operable communication with the erasure-check module that converts ECC encoded data in the second base into encoded data in the first base.