Error detection/correction and fault detection/recovery – Pulse or data error handling – Error/fault detection technique
Reexamination Certificate
2000-11-21
2004-06-01
Lamarre, Guy J. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Error/fault detection technique
C341S065000, C341S106000
Reexamination Certificate
active
06745366
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an N:N+1 channel coding method and apparatus therefor; and, more particularly, to a method and apparatus capable of correcting an error for N:N+1 channel codes in an increased code rate.
BACKGROUND OF THE INVENTION
As is well known, demands for optically storing a large amount of data, such as data for a motion picture film, have been increasing. 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.
In the VHDS system, source data are segmented into blocks of N data bits, which are also called information bits or message bits, each block capable of representing any of 2
N
distinct messages. An encoder in the VHDS system transforms each N-bit data block into a larger block of (N+K) bits, called code bits or channel symbols. The K bits, which the encoder adds to each data block, are called redundant bits, parity bits or check bits: they carry no new information.
The code is referred to as an (N+K, N) code. The ratio of redundant bits to data bits, K/N, within a block is called redundancy of the code, and the ratio of data bits to total bits, N/(N+K), is called a code rate. The code rate may be thought of as the portion of a code bit that constitutes information. For example, in a rate ⅓ code, each code bit carries ⅓ bit of information. If, for example, an error control technique employs a rate ⅓, the redundancy is ⅔ and the bandwidth expansion is only 3.
In other words, the encoder transforms a block of N message digits (a message vector) into a longer block of N+K codeword digits (a code vector), constructed from a given alphabet of elements. When the alphabet consists of two elements (0 and 1), the code is a binary code comprised of binary digits (bits). The explanation provided therein will be confined to binary codes, unless otherwise noted.
The N-bit message forms 2
N
distinct message sequences referred to as N-tuples (sequences of N digits). The (N+K)-bit blocks can form as many as 2
N+K
distinct sequences, referred to as (N+K)-tuples. The encoding procedure assigns to each of the 2
N
message N-tuples one of the 2
N+K
(N+K)-tuples. A block code represents a one-to-one assignment, whereby the 2
N
message N-tuples are uniquely mapped into a new set of 2
N
codeword (N+K)-tuples; and the mapping can be accomplished via a look-up table.
In the decoding mode, a multiplicity of decoding algorithms has been used in order to increase the code rate while decreasing the bit error rate.
In a threshold decoding algorithm, a threshold, e.g., an average value or a predetermined value such as 0.5, may be used to assign ‘0’ or ‘1’ to a retrieved or transmitted signal disturbed by channel distortion. In the conventional VHDS system, Gaussian distribution characteristics of a laser beam, lens distortions, scattering and diffraction in the system and so on may be appreciated as a channel. The threshold decoding algorithm has a higher code rate, but also has a higher bit error rate, specifically, with a lower intensity of laser beam.
An improvement may be realized by using a local threshold decoding algorithm. The local threshold decoding algorithm divides a decoding region into a plurality of local regions and applies a different threshold for each local region so as to determine ‘0’ or ‘1’. The local threshold decoding algorithm has a low compatibility because each of the VHDS systems has intrinsic noise patterns different from each other.
Another improvement may be realized by using a binary differential decoding algorithm. The binary differential decoding algorithm uses a characteristic that a signal for representing ‘1’ is always larger than a signal for representing its nearest ‘0’. For example, ‘0’ and ‘1’ are replaced with ‘01’ and ‘10’, respectively, to be encoded and its reverse algorithm is used to decode a transmitted signal. The binary differential decoding algorithm has a lower bit error rate, but its code rate is also comparatively decreased.
Another improvement may be achieved by employing a balanced block decoding algorithm. The balanced block decoding algorithm divides an input message into a plurality of message P-tuples and each message P-tuple is encoded with a codeword 2Q-tuple, wherein the number of lower bits is equal to that of higher bits, 2Q being larger than P. In a decoding mode, a transmitted signal is divided into a plurality of codeword 2Q-tuples; and Q number of lower and higher bits for each codeword 2Q-tuple are reconstructed as ‘0’ and ‘1’, respectively. For example, in a 6:8 balanced block decoding algorithm only 2
6
(=64) codeword 8-tuples which have the same number, i.e., 4 of lower and higher bits among
2
8
(=256) codeword 8-tuples are selected to encode 64 message 6-tuples. The balanced block coding algorithm has a lower bit error rate and a higher code rate than the binary differential coding algorithm; however, a still higher code rate is required to use a limited channel resource effectively.
SUMMARY OF THE INVENTION
It is, therefore, an object of the present invention to provide a method and apparatus capable of correcting an error for N:N+1 channel codes in an increased code rate.
In accordance with a preferred embodiment of the present invention, there is provided a method for correcting an error in N:N+1 channel codes, comprising the steps of:
(a) categorizing the 2
N+1
codeword (N+1)-tuples into M subsets of codeword (N+1)-tuples, wherein M is an integer larger than 1, each subset G has N
G
codeword (N+1)-tuples, N
G
being a positive integer, and the total number of codeword (N+1)-tuples in the M subsets is 2
N
given as follows:
∑
G
=
1
M
N
G
=
2
N
,
wherein said each subset G has a predetermined number K
G
of lower bits and a predetermined number (N+1−K
G
) of higher bits and the number of lower bits in every codeword (N+1)-tuple in any subset is not equivalent to that of lower bits in every codeword (N+1)-tuple in any other subset;
(b) matching said 2
N
message N-tuples with said 2
N
codeword (N+1)-tuples in said M subsets, respectively, in one-to-one correspondence to generate a lookup table.
(c) dividing an input message into a plurality of message N-tuples;
(d) encoding each message N-tuple with its corresponding codeword (N+1)-tuple based on the lookup table sequentially;
(e) assigning a subset parity (P−Q)-tuple to Q codeword (N+1)-tuples, wherein the subset parity (P−Q)-tuple is redundant bits for representing subset information of said Q codeword (N+1)-tuples and P is larger than Q, P and Q being integers; and
(f) transmitting the Q codeword (N+1)-tuples and the subset parity (P−Q)-tuple.
REFERENCES:
patent: 5740203 (1998-04-01), Ramaswamy et al.
Book: A. Yufa (Aleksandr Leybovich Yufa) “Automation of control processes of maneuvering surface objects”, Sudostroyenie (“Shpbuilding” Publishing House), 1987, Leningrad (St. Petersburg), USSR (Russia), 287 pages, pertinent pp. 197-203, 205-208.
Kang Byung-Bok
Roh Jae-Woo
Anderson Kill & Olick PC
Daewoo Electronics Corporation
Lamarre Guy J.
LandOfFree
Error correcting method and apparatus for N:N+1 channel... 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 correcting method and apparatus for N:N+1 channel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error correcting method and apparatus for N:N+1 channel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3336212