N:N+1 channel coding method and apparatus therefor

Details N:N+1 channel coding method and apparatus therefor N:N+1 channel coding method and apparatus therefor

2000-11-06

2002-02-12

JeanPierre, Peguy (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Coding by table look-up techniques

C341S065000

Reexamination Certificate

active

06346897

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 encoding binary data and decoding transmitted codeword data by using an N:N+1 channel coding algorithm with a higher 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 1/3 code, each code bit carries 1/3 bit of information. If for example, an error control technique employs a rate 1/3, the redundancy is 2/3 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 encoding binary data and decoding transmitted codeword data by using an N:N+1 channel coding algorithm with a much increased code rate with a reduced bit error rate.
In accordance with a preferred embodiment of the present invention, there is provided a method for mapping 2
N
message N-tuples into 2
N+1
codeword (N+1)-tuples, wherein said each of N-tuples and (N+1)-tuples is a binary code comprised of bits, 0 and 1, 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
,
 is wherein the 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; and
(b) matching the 2
N
message N-tuples with the 2
N
codeword (N+1)-tuples in the M subsets, respectively, in one-to-one correspondence to generate a lookup table.


REFERENCES:
patent: 5739779 (1998-04-01), Kunisa et al.
patent: 5920272 (1999-07-01), Schouhamer -Immink
patent: 6240213 (2001-05-01), Cho

Affiliated with

Also associated with

Rating

N:N+1 channel coding method and apparatus therefor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with N:N+1 channel coding method and apparatus therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and N:N+1 channel coding method and apparatus therefor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2935712