Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2001-04-09
2004-03-23
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C375S265000, C341S058000
Reexamination Certificate
active
06711711
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a channel coding; and, more particularly, to a method capable of detecting and correcting errors in data encoded with a pseudo-balanced code having a higher code rate.
BACKGROUND OF THE INVENTION
As is well known, the demand for a storage system capable of storing a large amount of optical data such as a motion picture film has been increased. Therefore, various types of volume holographic data storage (VHDS) systems incorporating therein a storage medium have been recently developed for realizing high density optical storage capabilities. Further, a coding technique capable of detecting and correcting errors by noisy or otherwise impaired channel has been also developed.
Convolutional codes are a class of channel codes used to mitigate the effects of channel noise in the transmission of information. A convolutional encoder in a transmitter is a finite-state machine whose operation may be described in terms of trellis. As it accepts data bits, the convolutional encoder proceeds through a sequence of states and produces an output which subsequently is used to define an output sequence of symbols that is transmitted over a noisy or otherwise impaired channel. The output sequence of symbols corresponds to a path through the trellis that describes such encoding operation.
A maximum-likelihood decoder for convolutional codes is known in the art as the Viterbi decoder. The Viterbi decoder determines the output sequence of symbols that was transmitted based on the received corrupted version of the transmitted sequence and knowledge of the code used by the encoder. This sequence corresponds to the “best path”, that is, the single path through the trellis having the best so-called path metric. For the Gaussian channel, for example the output sequence is determined by correlating with the received version all possible transmitted code sequences corresponding to paths through the trellis and then choosing, as the “maximum likelihood” sequence, the sequence where the correlation is maximum.
As it operates, the Viterbi decoder disregards a number of paths in the trellis and considers only the so-called surviving paths as candidates for the best path. Looking backwards in time or “tracing back”, the surviving paths tend to merge into the same predecessor path such that the value of an earlier received symbols may be decided. For so-called continuous Viterbi decoding, at any point in time a decision is made as to the value of an earlier received symbol by tracing back along the path identified as the best path at that time.
In the VHDS systems, variations in signal strength cause problems in detection. One possible solution to the problems in detection is the use of balanced codes. A balanced code is one in which each codeword is balanced-bit and contains exactly the same number of 1's as 0's. Since the number of 1's and 0's is balanced, the brighter 50% of samples are considered to be 1's and the dimmer 50% of the samples are considered to be 0's. In addition, the minimum Hamming distance, the minimum number of bits by which two distinct codewords differ, is 2. In the balanced code, a change in just one bit yields an invalid codeword because the result is unbalanced. To remain in balance, at least two bits must be changed.
FIG. 1
represents a trellis
100
of a conventional rate 8:12 balanced finite-state code capable of correcting an error. Trellis
100
has a plurality of state values which describe a sequence of state transitions. That is, trellis
100
has four top level states, state a, state b, state c and state d. Likewise, trellis
100
has four bottom level states, state a, state b, state c and state d, which are the same states as the top level states. Each transition in trellis
100
represents a set of 64 balanced codewords of length
12
. There are eight such sets, assigned to the transitions as shown in Table A.
TABLE A
Bottom State
Top State
a
b
c
d
a
S
1
S
2
S
3
S
4
b
S
5
S
6
S
7
S
8
c
S
2
S
1
S
4
S
3
d
S
6
S
5
S
8
S
7
Each set, S
1
, (i=1, 2, . . . , 8) is an arbitrary set of 64 balanced binary codewords, each codeword being represented by 12 bits of b
0
b
1
b
2
. . . b
11
, where b
1
+2b
2
+3b
3
. . . +11b
11
−i is a multiple of 12.
This code has a minimum distance of 4, which provides considerable error-detecting and correcting capability in the presence of noise. However, there is a problem in the use of the rate 8:12 balanced finite-state code. That is, the rate 8:12 balanced finite-state code scheme has a lower code rate, i.e., about 67%. Therefore, there is a need for a coding scheme having an error-correcting capability and a higher code rate.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide a coding scheme having an error-correcting capacity and a higher code rate.
In accordance with one embodiment of the present invention, there is provided a method for encoding a series of M-bit message words into a series of N-bit codewords having a bounded unbalance, a part of the message words being used to index bits and others source words, wherein the M and N are positive integer and the N is larger than the M, comprising steps of: grouping the message words to a plurality of subsets using the index bits; classifying the unbalanced codewords to a plurality of sets based on a state transition in a trellis having states and levels, each of the classified unbalanced codewords being stored at a codebook for each codeword set, respectively, the codebook having the source words, a codeword ID for each of the source words and the classified unbalanced codewords;
encoding the message words into the respective codeword in the codebook, respectively, by using the index bits of the message words and the state transition in the trellis, the codewords being selected by transition for each state at each level of the trellis based on correlations.
In accordance with another embodiment of the present invention, there is provided a method for decoding a codeword, which is encoded by the above encoding method, from a series of data word representing intensities of an analog signal, comprising steps of: receiving the data word; calculating branch metrics between the data word and each codeword in the codeword set classified by the state transition in the trellis to obtain minimum branch for each bottom states; figuring out path metric for each bottom state based on the calculated branch metrics to select a minimum path metric thereamong for each bottom state in the trellis; selecting a best path having the smallest path metric having states and decoding stages; tracing back the selected best path and decoding a codeword corresponding to a state transition into a message word by using the codeword ID in the codebook.
REFERENCES:
patent: 5263033 (1993-11-01), Seshadri
patent: 5388124 (1995-02-01), Laroia et al.
patent: 6504877 (2003-01-01), Lee
patent: 6535647 (2003-03-01), Abousleman
Lattice and Trellis Quantization with Lattice- and Trellis-Bounded Codebooks-High-rate Theory for Memoryless Sources Eyuboglu et al.Information Theory, IEEE Transactions on, vol.: 39 Issue: 1, Jan. 1993 pp. 46 -59.
Britt Cynthia
De'cady Albert
LandOfFree
Error correctible channel coding method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Error correctible channel coding method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correctible channel coding method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3207976