N:N+1 channel coding method and apparatus therefor

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.

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.

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.

The above and other objects and features of the present invention will become apparent from The following description of preferred embodiments given in conjunction with the accompanying drawings, in which:

FIG. 1 represents a block diagram for illustrating a holographic digital encoding and decoding system in accordance with the present invention;

FIG. 2A shows a flow chart for illustrating an encoding algorithm for encoding a message N-tuple into a codeword (N+1)-tuple in accordance with the present invention;

FIG. 2B describes a flow chart for illustrating a decoding process for decoding a transmitted codeword (N+1)-tuple into a reconstructed message N-tuple in accordance with the present invention;

FIG. 3 provides a graph for relations between signal-to-noise ratio (SNR) to bit error rate (BER) of various channel decoding algorithms; and

FIG. 4 presents a graph for relations between BER and capacity gain of various channel decoding algorithms.

Referring to FIG. 1, there is shown a block diagram for illustrating a holographic digital encoding and decoding system in accordance with a preferred embodiment of the present invention, wherein the system comprises a holographic data storage (HDS) circuit 110 , an encoding circuit 130 , a lookup table generator 140 and a decoding circuit 150 . Specifically, the HDS system 110 has a laser 111 , a beam splitter 112 , a first and a second shutter 113 and 116 , a first and a second mirror 114 and 117 , an actuator 115 , a spatial light modulator(SLM) 118 , a storage medium 119 and a charge coupled device(CCD) 120 . The encoding circuit 130 has an N-tuple generator 132 and a encoding unit 134 . The lookup table generator 140 has a categorization unit 142 and a matching unit 144 . The decoding circuit 150 has a dispersion calculation unit 154 , a set determination unit 156 and a reconstruction unit 158 .

In the HDS system 110 , a laser beam emitted from the laser 111 impinges onto the beam splitter 112 which is capable of partially reflecting the laser beam to thereby obtain a reference and a signal beam, wherein the reference beam is a portion of the laser beam transmitted through the beam splitter 112 and the signal beam is a remaining portion of the laser beam reflected from the beam splitter 112 .

The reference beam enters into the storage medium 119 through a reference beam path (PS 1 ) after being reflected by the first mirror 114 controlled by the actuator 115 . In the meantime, the signal beam enters into the SLM 118 which converts the signal beam impinged thereonto into a modulated signal beam through a signal beam path (PS 2 ) after being reflected by the second mirror 117 , wherein the modulated signal beam carries data in the form of pages after passing through the SLM 118 . The modulated signal beam is focused on the storage medium 119 . In the storage medium 119 , the modulated signal beam interferes with the reference beam to thereby generate an interference pattern therebetween, wherein the interference pattern contains information of the modulated signal beam. The interference pattern is converted to an optical index pattern in the storage medium 119 whose refractive index changes in response to the interference pattern to thereby record the modulated signal beam into the storage medium 119 .

To read the stored data, only the first shutter 113 remains open while the second shutter 116 turns to be closed so that the modulated signal beam retrieved from the storage medium 119 enters the CCD 120 which is capable of detecting the power of the retrieved signal beam. The retrieved signal beam is generated by diffraction of the reference beam from the storage medium 119 .

In the meantime, the categorization unit 142 for implementing an N:N+1 encoding algorithm in the lookup table generator 140 selects M subsets of codeword (N+1)-tuples among 2 N−1 codeword (N+1)-tuples, wherein information on the M subsets of codeword (N+1)-tuples is transferred to the matching unit 144 .

M is an integer larger than 1 and preferably an even integer. Each subset G has a predetermined number K G of lower binary digits and a predetermined number (N+1−K G ) of higher binary digits. The number of lower binary digits in every codeword (N+1)-tuple in any subset is not equivalent to that of lower binary digits in every codeword (N+1)-tuple in any other subset.

If each subset G has N G number of codeword (N+1)-tuples, N G being a positive integer, the total number of codeword (N+1)-tuples in the M subsets must be 2 N . In other word, ∑ G = 1 M  N G = 2 N .

It is preferable that the number N G is equal to 2 N /M. The matching unit 144 matches the 2 N message N-tuples with the 2 N codeword (N+1)-tuples in the M subsets in one-to-one correspondence to generate a lookup table between 2 N message N-tuples and the 2 N codeword (N+1)-tuples. The lookup table is shared with the encoding unit 134 and the reconstruction unit 158 .

In the meantime, the N-tuple generator 132 receives input message and sequentially divides the input message into a plurality of message N-tuples. The plurality of message N-tuples are provided to the encoding unit 134 .

The encoding unit 134 encodes each message N-tuple in the plurality of message N-tuples with its corresponding codeword (N+1)-tuple based on the lookup table to generate a plurality of codeword (N+1)-tuples. The plurality of codeword (N+1)-tuples are transmitted to the SLM 118 which converts the signal beam impinged thereonto into a modulated signal beam. The modulated signal beam is focused on the storage medium 119 . In the storage medium 119 , the modulated signal beam interferes with the reference beam to thereby generate the interference pattern therebetween as described above.

To read the stored data, the modulated signal beam retrieved from the storage medium 119 enters the CCD 120 which is capable of detecting the power of the retrieved signal beam. The SLM 118 , the storage medium 119 and the CCD 120 may be appreciated as a channel. The retrieved signal beam is transmitted to the dispersion calculation unit 154 and the set determination unit 156 as a plurality of transmitted codeword (N+1)-tuples. Each transmitted codeword (N+1)-tuple has been disturbed by internal and external noises during a transmitted process through the channel so that it may be represented by (N+1) decimals.

The dispersion calculation unit 154 calculates a dispersion for (N+1) decimals of each codeword (N+1)-tuple. Firstly, a least number L of higher and lower bits in M subsets of codeword (N+1)-tuples is calculated and a greatest number K is computed from the least number L and the subset number M. Specifically, the greatest number K is a maximum value of the least number L and the ceiling of Log 2 M, i.e., ┌Log 2 M┘. Maximum or minimum decimals as many as the greatest number K are deleted in (N+1) decimals so that (N+1−K) decimals may be obtained for each transmitted codeword (N+1)-tuple. An (N+1−K)th dispersion for the (N+1−K) decimals is calculated by using a conventional dispersion calculation method to obtain a plurality of (N+1−K)th dispersions for a plurality of transmitted codeword (N+1)-tuples. If necessary, other dispersions may be calculated by changing the greatest number K. If the subset number M is larger than 2, additional dispersion is required. Information on the dispersions is delivered to the set determination unit 156 .

The set determination unit 156 determines which subset G corresponds to the transmitted codeword (N+1)-tuple based on the information on the dispersions. Specifically, an (N+1−K)th average dispersion for the plurality of (N+1−K)th dispersions is calculated and each (N+1−K) dispersion is compared with the (N+1−K)th average dispersion. The subset G corresponding to the transmitted codeword (N+1)-tuple may be determined based on the dispersion comparison result.

The reconstruction unit 158 reconstructs a reconstructed codeword (N+1)-tuple based on information on the subset G. Specifically, a predetermined number K G of lower decimals in the transmitted codeword (N+1)-tuple are converted into the lower binary digit and a predetermined number (N+1−K G ) of higher decimals are converted into the higher binary digit. A reconstructed message N-tuple is assigned for the reconstructed codeword (N+1)-tuple based on the lookup table delivered from the matching unit 144 .

Referring to FIG. 2A, there is shown a flow charl for illustrating an encoding algorithm for encoding a message N-tuple into a codeword (N+1)-tuple in accordance with the present invention.

At step S 21 , M subsets of (N+1)-tuples are selected among 2 N+1 codeword (N+1)-tuples. M is an integer larger than 1 and preferably an even integer. Each subset G has a predetermined number K G of lower binary digits and a predetermined number (N+1−K G ) of higher binary digits. The number of lower binary digits in every codeword (N+1)-tuple in any subset is not equivalent to that of lower binary digits in every codeword (N+1)-tuple in any other subset. For example, 2 4 (=16) codeword 4-tuples may be categorized into 5 subsets of 4-tuples, i.e., {0000}, {0001, 0010, 0100, 1000}, {0011, 0101, 1001, 0110, 1010, 1100}, {0111, 1011, 1101, 1110} and {1111}, based on the number of ‘0’s or ‘1’s.

If each subset G has N G number of codeword (N+1)-tuples, N G being a positive integer, the total number of codeword (N+1)-tuples in the M subsets must be 2 N . In other word, ∑ G = 1 M  N G = 2 N .

It is preferable that the number N G is equal to 2 N /M. Therefore, in order to use 2 subsets of codeword 4-tuples in 3:4 encoding process, the number N G of codeword 4-tuples in each subset is preferably 4(=2 3 /2) so that two subsets are preferably selected among three subsets having at least 4 4-tuples, i.e., {0001, 0010, 0100, 1000}, {0011, 0101, 1001, 0110, 1010, 1100} and {0111, 1011, 1101, 1110}.

At step S 23 , the 2 N message N-tuples are matched with the 2 N codeword (N+1)-tuples in the M subsets in one-to-one correspondence to generate a lookup table between 2 N message N-tuples and the 2 N codeword (N+1)-tuples.

At step S 25 , input message is sequentially divided into a plurality of message N-tuples.

At step S 27 , each message N-tuple in the plurality of message N-tuples is encoded with its corresponding codeword (N+1)-tuple based on the lookup table sequentially and, at step S 29 , a plurality of codeword (N+1)-tuples are transmitted through a channel.

Referring to FIG. 2B, there is shown a flow chart for illustrating a decoding process for decoding a transmitted codeword (N+1)-tuple into a reconstructed message N-tuple in accordance with the present invention.

At step S 31 , a plurality of transmitted codeword (N+1)-tuples are sequentially received. Each transmitted codeword (N+1)-tuple has disturbed by internal and external noises during a transmitted process through the channel so that it may be represented by (N+1) decimals.

At step S 33 , the least number L of higher and lower bits in M subsets of codeword (N+1)-tuples is calculated, wherein M subsets of codeword (N+1)-tuples have been selected in 2 N+1 codeword (N+1)-tuples as described at step S 21 . When M subsets of codeword (N+1)-tuples are determined, the least number L is concurrently defined arid delivered to both the encoding circuit 130 and the decoding circuit 150 in accordance with the present invention. For each codeword 4-tuple in a subset {0001, 0010, 0100, 1000}, for example, the number of higher bits and the number of lower bits are 1 and 3, respectively, so that the least number L is 1.

At step S 35 , a greatest number K is computed from the least number L and the subset number M. Specifically, the greatest number K is a maximum value of the least number L and the ceiling of Log 2 M, i.e., ┌Log 2 M┘. If the least number L is 1 and the subset number M is 4, ┌Log 2 4┘=2 so that the greatest number K is 2.

At step S 37 , maximum or minimum decimals as many as the greatest number K are deleted in (N+1) decimals so that (N+1−K) decimals may be obtained for each transmitted codeword (N+1)-tuple. If K is 1 and 4 decimals of a transmitted codeword 4-tuple are {0.1, 0.3, 0.6, 0.2}, then 0.6 is deleted to obtain 3 decimals {0.1, 0.3, 0.2}.

At step S 39 , an (N+1−K)th dispersion for tne (N+1−K) decimals is calculated by using a conventional dispersion calculation method to obtain a plurality of (N+1−K)th dispersions for a plurality of transmitted codeword (N+1)-tuples.

At step S 41 , an (N+1−K)th average dispersion for the plurality of (N+1−K)th dispersions is calculated and each (N+1−K)th dispersion is compared with the (N+1−K)th average dispersion. Specifically, it is determined whether each (N+1−K)th dispersion is larger than the (N+1−K)th average dispersion or not.

At stop S 43 , Log 2 M and the least number L are decreased by 1. In other word, Log 2 M and L are replaced with Log 2 M-1 and L-1, respectively.

At step S 45 , it is determined if Log 2 M is larger than 0 and the least number L is larger than or equal to 0. If Log 2 M>0 and L≧0, the process goes back to step S 35 and, if otherwise, the process goes to step S 47 .

At step S 47 , it is determined which subset G corresponds to the transmitted codeword (N+1)-tuple based on the dispersion comparison result obtained at step S 41 .

At step S 49 , in order to reconstruct a reconstructed codeword (N+1)-tuple based on information on the subset G determined at step S 47 , a predetermined number K G of lower decimals in the transmitted codeword (N+1)-tuple are converted into a lower binary digit and a predetermined number (N+1−K G ) of higher decimals are converted into a higher binary digit.

At step S 51 , a reconstructed message N-tuple is assigned for the reconstructed codeword (N+1)-tuple based on the lookup table.

Referring to FIG. 3, there is shown a graph for relations between signal-to-noise ratio (SNR) and bit error rate (BER) of various channel decoding algorithms. The threshold decoding algorithm, the binary differential decoding algorithm, the balanced block decoding algorithm and the 3:4 channel decoding algorithm in accordance with the present invention are illustrated as T, BD, BB and 3:4, respectively. The SNR represents a degree of separability between higher bit and lower bit. and is calculated as follows: SNR = ρ w - ρ b σ w 2 + σ b 2

wherein ρ w , ρ b , σ w and σ b are an average of higher bit, i.e., ‘1’, an average of lower bit, i.e., ‘0’, a standard deviation of higher bit and a standard deviation of lower bit, respectively. The SNR to BER characteristic of the 3:4 channel decoding algorithm in accordance with the present invention is comparatively good.

Referring to FIG. 4, there is shown a graph for relations between BER and capacity gain of various channel decoding algorithms. The capacity gain is calculated as follows: Capacity     gain = m n  1 SNR

wherein m/n is code rate and m is larger than n. The capacity characteristic of the present invention is superior to those of the other decoding algorithm.