Two-dimensional DC-free encoder and decoder

[0002] The invention relates to data storage. More specifically, the invention relates to modulation encoding of data prior to storage on a recordable medium.

[0003] In magnetic and optical memory devices, sectors of user data are typically encoded prior to storage on recordable media. The sectors are arranged into blocks, and the blocks of user data are encoded for forward error correction. Redundancy data such as error correction codewords are added to the user data, thereby forming Error Correction Codeword (“ECC”) blocks. The redundancy data allows for forward error correction of user data that, after retrieval, has been found to contain errors (for example, due to an error on the storage medium).

[0004] The ECC blocks are then modulation encoded. During modulation encoding, slices of bits (hereinafter referred to as “messages”) of the blocks are mapped into distinct symbols. For instance, 8-bit messages might be mapped into distinct 16-bit symbols or codewords. One popular modulation code is a “(2,10)-Run Length Limited” code.

[0005] Blocks of these codewords are then written to a storage medium. In the case of a hard drive, the codewords are typically arranged on a platter in concentric tracks. In the case of an optical disc such as a CD or DVD, the data is stored in a spiral groove in a substrate (and perhaps on lands too). In both cases, the data storage is one-dimensional.

[0006] Recent proposals for the design of optical storage-in particular holographic memory design-have attempted to take advantage of the fact that the recording surface of the media is actually two-dimensional. Storing data in two dimensions instead of one dimension would allow recording density to be increased.

[0007] Adding the additional dimension to encoding, however, introduces new types of constraints on the recorded data. Experiments reported on holographic memory, and experience gathered in other existing optical devices, suggest that the number of 0's and 1's in the recorded data should be balanced within certain areas or patterns. If data is recorded in two-dimensional n×m rectangular arrays (that is, arrays having n rows and m columns), one constraint of potential interest requires that every row and column of the recorded array be balanced. A row or column or, more generally, a vector having 0,1 entries is balanced if it has the same number of 0's and 1's. Such arrays shall be referred to as balanced arrays. Thus, the problem becomes one of encoding unconstrained (binary) messages into distinct n×m balanced arrays of recorded data.

[0008] Lowering the redundancy of the encoding algorithm makes it more efficient since it can represent a greater number of messages using a given array size, and hence a given area on the storage medium. A two-dimensional encoding algorithm for balanced arrays has been proposed in a paper by R. Talyansky, T. Etzion and R. M. Roth in “Efficient code constructions for certain two-dimensional constraints,” IEEE Trans. Inform. Theory, 45 (1999), pp. 794-99.

[0009] An encoding algorithm that achieves a smaller redundancy would be desirable. Reducing the redundancy would allow a greater number of messages to be packed into n×m balanced arrays. This, in turn, would allow more data to be placed on the tracks. Reducing the redundancy would also allow tracks to be spaced closer together. Thus, reducing the redundancy in two dimensions would allow storage density to be increased.

[0010] A message is encoded into a corresponding constrained array, which is an element of a set of distinct constrained arrays. A column-wise method of encoding a message into a corresponding array of the constrained array set may be performed by (a) considering a predetermined ordering of candidates for a j^thcolumn of the corresponding array, where j is a positive integer; (b) for each candidate being considered, computing a lower bound on the number of constrained arrays having that candidate as the j^thcolumn and any previously selected columns of the corresponding array as the first j−1 columns; (c) determining an index range for each candidate being considered, upper and lower limits of each index range being based upon the lower bounds of the candidates being considered; (d) determining the range in which an intermediate message lies; and (e) selecting the candidate corresponding to the determined range as the j^thcolumn of the corresponding array.

[0011] In the alternative, a bit-wise method of encoding a message into a corresponding array of the constrained array set may be performed by (a) determining a lower bound on the number of constrained arrays with a 0 as the k^thbit of the j^thcolumn and the first k-1 bits of the j^thcolumn and first j−1 columns being equal to previously selected entries of the corresponding array; and (b) setting the value of the k^thbit of the corresponding array depending upon the value of the lower bound relative to an intermediate message. Steps (a) and (b) are performed for each bit in the corresponding array.

[0012] Such encoding of messages into constrained arrays achieves a lower redundancy than encoding according to the algorithm mentioned above in the Roth et al. paper. The reduction of redundancy allows storage density to be increased.

[0013] Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.

[0014] FIG. 1 is an illustration of a read/write device that performs two-dimensional encoding in accordance with the present invention;

[0015] FIG. 2 is a flowchart of a method of performing initialization steps for the two dimensional encoding in accordance with the present invention;

[0016] FIG. 3 is a flowchart of a column-wise method for encoding a message into an n×m balanced array in accordance with the present invention;

[0017] FIG. 4 is a flowchart of a column-wise method for decoding an n×m balanced array in accordance with the present invention;

[0018] FIG. 5 is a flowchart of a bit-wise method for encoding a message into an n×m balanced array in accordance with the present invention;

[0019] FIG. 6 is a flowchart of a bit-wise method for decoding an n×m balanced array in accordance with the present invention; and

[0020] FIGS. 7(a) and 7(b) are illustrations of possible hardware implementations for the methods in accordance with the present invention.

[0021] As shown in the drawings for purposes of illustration, the present invention is embodied in a drive that can write data to a recordable medium. The drive can perform two-dimensional modulation-encoding, in which messages are encoded into distinct n×m arrays. The n×m arrays are balanced, and therefore dc free when 0's and 1's are mapped to equal magnitude signals with opposite polarity. Moreover, redundancy of the encoding is lower than previously reported. As a consequence of reducing the redundancy, a greater number of messages can be packed into n×m arrays. This, in turn, allows more information to be stored on the medium. Reducing the redundancy of the encoding allows storage density to be increased.

[0022] FIG. 1 shows a drive 10 for writing data to an optical disc 12. The drive 10 includes a controller 16 for receiving a mode of operation from a host 14 (e.g., a personal computer). Typical modes of operation include a read mode and may include various write modes such as a write-append mode and an insert-edit mode.

[0023] The drive 10 further includes a spindle motor 18 and motor control 20 for rotating the disc 12. The drive 10 further includes an optical pickup unit 22, which typically includes a laser for generating a laser beam B1; and means (e.g., an optics assembly and photodetector array) for detecting a modulated beam B2. The optical pickup unit 22 generates a readback signal RBK carrying data and timing/addressing information.

[0024] The laser of the optical pickup unit 22 is driven by a laser driver 24. Power of the laser beam B1 depends upon the mode of operation of the drive 10. The laser power is controlled between various levels including a read level for reading data from the disc 12, an erase level for erasing data on the disc 12, and a write level for writing data to the disc 12. A processor 26 receives the readback signal RBK from the optical pickup unit 22.

[0025] A tracking servo 27 receives the readback signal RBK from the processor 26. The tracking servo 27 moves the optical pickup unit 22 along the disc 12.

[0026] During read mode, a conventional data recovery circuit 28 receives an electrical signal from the processor 26 and recovers data from the electrical signal. A decoder 30 demodulates the recovered data, arranges the demodulated data into ECC blocks in RAM 32, and performs error correction on the ECC blocks. Error-corrected user data is sent to the host 14.

[0027] During a write mode, user data is sent by the host 14 to the controller 16, which buffers the user data in RAM. Under control of the controller 16, an encoder 34 adds redundancy data to the user data and then performs two-dimensional modulation encoding on the ECC blocks. During the modulation encoding, a plurality of messages (e.g., bit slices) are obtained from the ECC blocks and the messages are encoded into constrained arrays. The constrained arrays may be balanced.

[0028] The controller 16 has the encoder 34 send the modulation-encoded data to the laser driver 24, and it commands the laser driver 24 to begin writing the data to the disc 12 (e.g., the controller 16 enables a write clock generator to send a write clock to the laser driver 24). The laser driver 24 causes the laser in an optical pickup unit 22 to write the data to the disc 12.

[0029] FIGS. 2 and 3 illustrate a method of performing the two-dimensional encoding of messages that are members of the message set U. Each message u in the set U is encoded into a corresponding n×m balanced array E(u) belonging to the balanced array set C. The encoding method will first be described in terms of a column selection procedure given integers n and m and a message u.

[0030] FIG. 2 illustrates initialization steps that are performed prior to the encoding. First, a lower bound on the number of arrays in the balanced array set C is determined (block 102). Let the row type of a binary array be the integer n-vector with entries specifying the number of 1's in the corresponding rows of the array. Thus, if the row type of an array is the integer n-vector w=(w₁, . . . , w_n), then the i^throw has w_i1's for i=1. . . n. For example, an array having row type w=(4, 4, . . . , 4) will have four 1's in the first row, four 1's in the second row and four 1's in the n^throw.

[0031] Now let R_m(w) be the set of all binary n×m arrays having rows of type vector w. The cardinality of R_m(w), denoted by |R_m(w)| is given by equation (1). $\begin{array}{cc}\left|R_m\left(w\right)\right|=\prod _{i=1}^n\left(\begin{array}{c}m\\ w_i\end{array}\right)& \left(1\right)\end{array}$

[0032] For even values of n and an integer n-vector w with components summing to nm/2, let M_m(w) denote the set of all arrays in R_m(w) having balanced columns (n/2 1's and n/2 0's in every column). For even m, the set C of balanced n×m arrays is equivalent to the constraint set M_m(w) with w=(m/2, . . . , m/2). Thus, an encoder mapping messages u into balanced arrays E(u) is obtained as a special case of an encoder that maps messages u into arrays belonging to the set M_m(w). This more general encoder is described next.

[0033] First a lower bound on the number of arrays satisfying the constraints, in this case the number of arrays in the set M_m(w), is computed. A lower bound on the cardinality of M_m(w), denoted by |M_m(w)|, is given by the formula (λ_n)^m|R_m(w)|, where λ_nmay be determined according to equation (2). $\begin{array}{cc}{\lambda }_n=\frac{\left(\begin{array}{c}n\\ n/2\end{array}\right)}{2^n}& \left(2\right)\end{array}$

[0034] Next, the message range is determined (block 104). The message range may be determined according to equation (3).

[0035] 0≦u<(λ_n)^m|R_m(w)|  (3)

[0036] Thus, the number of distinct messages u in the message set U must be at most (λ_n)^m|R_m(w)|, the determined lower bound on the cardinality of the set of constrained arrays M_m(w). If the message u is a binary word, the length of the message u may be the integer portion of log₂((λ_n)^m|R_m(w)|).

[0037] The set V of column candidates may also be determined during initialization (block 106). For the constraint set M_m(w), the candidates set V consists of all of the balanced n dimensional binary vectors. When n=4, for example, the candidates set V for consideration consists of (0,0,1,1), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,0,1,0) and (1,1,0,0).

[0038] Reference is now made to FIG. 3, which shows the encoding method according to the present invention. At the start of encoding (block 200), a message u is supplied to the encoder 34. The message u may be an integer within the range computed in the initialization step. Thus, the message may be a binary string, which, for encoding purposes, can be interpreted as an integer in binary notation.

[0039] The n×m balanced array E(u) into which the message u is mapped is determined one column at a time according to an iterative procedure. Each step of the iterative procedure determines a new column of E(u) based on the above formulas and the values of two intermediate state variables: an intermediate message u′ and intermediate row type w′. These intermediate state variables u′ and w′ are updated after each iteration in preparation for determining the next column. The intermediate message u′ holds an updated message and is initialized to u′=u, the message being encoded. The intermediate row type w′ holds the row type of the yet-to-be determined portion of the constrained array E(u) and is initialized to w′=w, the initial row type defining the constraint. Assume j−1 columns e₁to e_j−1of the balanced array E(u) have already been selected. The j^thcolumn is determined as follows. A predetermined ordering of candidates in the set V for the j^thcolumn is considered (block 202). For each candidate y being considered in the candidates set V, a lower bound on the number of constrained arrays in the set M_m(w) having that candidate y as the j^thcolumn and the previously selected j−1 columns e₁, . . . , e_j−1is computed (block 204). In the case of arrays belonging to M_m(w), this lower bound is given by

[0040] λ_n^m−j|R_m−j(w′−y)|  (4)

[0041] where w′ is the row type of the n×(m−j+1) yet-to-be selected portion of the balanced array E(u) (as implied by the starting row type w and the previously selected columns e₁, . . . , e_j−1). If the candidate y is the first column of the n×(m−j+1) portion of the array E(u) that has yet-to-be selected, then w′−y is the row type of the remaining n×(m−j) portion of the array E(u).

[0042] Next, a lower limit σ_L(y) of the index range is determined for each candidate y being considered (block 206). The lower limit σ_L(y) may be determined by equation (5): $\begin{array}{cc}{\sigma }_L\left(y\right)={\lambda }_n^{m-j}\sum _{v<y}\left|R_{m-j}\left(w^{\prime }-v\right)\right|& \left(5\right)\end{array}$

[0043] where the sum is over all balanced binary vectors v appearing before y in the ordering. Thus, equation (5) provides a lower bound on the number of arrays in M_m(w) starting with the previously selected columns e₁. . . e_j−1and having a j^thcolumn that appears before y in the predetermined ordering.

[0044] The upper limit σ_L(y) of the index range corresponding to candidate y is equal to the lower limit corresponding to the candidate y plus the lower bound of the candidate (block 208). The upper limit σ_L(y), for all but the maximal y, is equal to the lower limit of the candidate immediately following candidate y in the ordering. There will be one or more non-zero values for σ_u(y).

[0045] Next, the range in which the intermediate message u′ lies is determined (block 210). The candidate y satisfying σ_u(y)≦u′<σ_U(y) is selected as the j^thcolumn e_jof the corresponding balanced array E(u) (block 212). This is equivalent to determining the largest candidate y, in terms of the predetermined ordering, which satisfies σ_L(y)≦u′.

[0046] If j<m (block 214), then additional columns e_j+1to e_mfor the balanced array E(u) are selected. Therefore, the intermediate message u′ is updated by subtracting from it the smallest integer that is greater than or equal to the lower limit of the range of the selected candidate e_j(that is, u′=u′−┌σ_L(e_j)┐) (block 216); the column index j is incremented to j+1 (block 218); the intermediate row type w′ is updated to w′=w′−e_j(block 220); and control is returned to the first block (block 202).

[0047] When updating the intermediate message u′, its new value is the integer portion of u′−σ_L(e_j), which is denoted by int(u′−σ_L(e_j)). In the alternative, the intermediate message u′ may be updated simply according to u′=u′−σ_L(e_j) so that in future iterations u′ might not necessarily be an integer. The above steps still apply, but a different encoding may result.

[0048] If j=m (block 214), w′ becomes the last column e_mof the balanced array E(u) (block 222), whereby the modulation encoding is finished (block 224).

[0049] A simple example of this column-wise two-dimensional modulation encoding will now be provided. The example will be described in connection with a 4×4 balanced array encoder, which encodes a set U of messages into a set C of balanced 4×4 arrays. Thus, n=4 and m=4. The row type and column type of the arrays in the set C are equal to w=(2,2,2,2).

[0050] Before the encoding begins, the initialization steps are performed to establish the message range. Applying equation (1): $R_4\left(2,2,2,2\right)=\left(\begin{array}{c}4\\ 2\end{array}\right)\left(\begin{array}{c}4\\ 2\end{array}\right)\left(\begin{array}{c}4\\ 2\end{array}\right)\left(\begin{array}{c}4\\ 2\end{array}\right)=\frac{\left(4\right)\left(3\right)\left(2\right)\left(1\right)}{\left(2\right)\left(1\right)\left(2\right)\left(1\right)}\left(6\right)\left(6\right)\left(6\right)=6^4$

[0051] Thus, there are R₄=6⁴ways of putting two 1's in each row of a 4×4 array.

[0052] Applying equation (2): ${\lambda }_4=\frac{\left(\begin{array}{c}4\\ 2\end{array}\right)}{2^4}=\frac{6}{16}=\frac{3}{8}$

[0053] The number λ₄is the probability that two out of four randomly selected binary elements (each taking the value one with probability ½) are equal to one.

[0054] Applying equation (3), $0\le u<{\left(\frac{3}{8}\right)}^4\left(6^4\right)\mathrm{or}0\le u<25.6$

[0055] Thus, the message range is between 0 and 25.6.

[0056] Since a 5-bit word can take on thirty two (2⁵) values, and since, from the above range, the 4×4 balanced array encoder can handle only up to 25 messages, the length of each message u in the message set U is restricted to four bits. Therefore, only sixteen balanced arrays would be needed to cover the sixteen possible values of a four-bit message u. Accordingly, the controller 16 would be configured to send four-bit slices of the ECC-encoded blocks to the encoder 34, and the encoder 34 would be configured to encode each four-bit message u into a corresponding one of sixteen balanced arrays E(u) in the balanced array set C.

[0057] There are six ways of putting two ones into a single column of a 4×4 balanced array. Therefore, a set V of six candidates in which 1's and 0's are balanced will be considered for each column of the balanced array E(u). The six candidates appearing in the predetermined order to be used in the encoding are v⁽¹⁾=(0,0,1,1); v⁽²⁾=(0,1,0,1); v⁽³⁾=(0,1,1,0); v⁽⁴⁾=(1,0,0,1); v⁽⁵⁾=(1,0,1,0); and v⁽⁶⁾=(1,1,0,0). This ordering corresponds to a lexicographic ordering in which v⁽ⁱ⁾<v^(j)if and only if v⁽ⁱ⁾is 0 and v^(j)is 1 in the first position from the left in which they differ.

[0058] The encoding of a message u=10 (that is, 1010₂) is performed as follows. A first iteration (j=1) is performed, where w′=w=(2,2,2,2) and u′=u=10. The first candidate y=v⁽¹⁾=(0,0,1,1) is considered (see Table 1). This establishes the lower limit on the index range for the first candidate v⁽¹⁾=(0,0,1,1).

[0059] The second candidate v⁽²⁾=(0,1,0,1) is then considered (see Table 2).

[0060] Therefore, the index range of the first candidate v⁽¹⁾is [0,4.3). Additionally, the lower limit on the index range of the second candidate v⁽²⁾is 4.3.

[0061] The third candidate v⁽³⁾=(0,1,1,0) is then considered as shown in Table 3.

[0062] Therefore, the index range of the second candidate v⁽²⁾is [4.3,8.5). Additionally, the lower limit on the index range of the third candidate v⁽³⁾is 8.5.

[0063] The fourth candidate v⁽⁴⁾=(1,0,0,1) is then considered (see Table 4).

[0064] Therefore, the index range of the third candidate v⁽³⁾is [8.5,12.8).

[0065] At this point, there is no need to consider the remaining candidates v⁽⁵⁾and v⁽⁶⁾. The intermediate message u′=10 lies in the index range corresponding to the third candidate (i.e., u′ satisfies 8.5≦u′<12.8). Therefore, the third candidate v⁽³⁾is selected as the first column e₁for the 4×4 balanced array E(10), which corresponds to the message u=10. After the first iteration, $E\left(10\right)=\begin{array}{cccc}0& \cdots & \cdots & \cdots \\ 1& \cdots & \cdots & \cdots \\ 1& \cdots & \cdots & \cdots \\ 0& \cdots & \cdots & \cdots \end{array}$

[0066] The intermediate message u′ is updated to u′=int (10−8.5)=1, the index j is incremented to 2, the intermediate row type w′ is updated to w′=w′−e₁, and another iteration is performed.

[0067] For the second iteration, the first, second and third candidates v⁽¹⁾, v⁽²⁾and v⁽³⁾are considered (see Table 5). The updated intermediate message u′ lies in the range [0.6,1.1) corresponding to the second candidate v⁽²⁾. Therefore, the second candidate v⁽²⁾is selected as the second column of the 4×4 balanced array E(10).

[0068] Thus, after the second iteration, $E\left(10\right)=\begin{array}{cccc}0& 0& e_{1,3}& e_{1,4}\\ 1& 1& e_{2,3}& e_{2,4}\\ 1& 0& e_{3,3}& e_{3,4}\\ 0& 1& e_{4,3}& e_{4,4}\end{array}$

[0069] (A quick examination would indicate that the values for both cells e_1,3and e_1,4will be 1, and that the values for both cells e_2,3and e_2,4will be equal to 0.) The intermediate message u′ is updated to u′=int (1−0.6)=0, the index j is incremented to 3, the intermediate row type w′ is updated to w′=w′−e₂, and another iteration is performed.

[0070] Since the updated intermediate message u′=0, the candidate corresponding to the first index range having a non-zero upper limit is selected. For the third iteration, the candidates v⁽¹⁾, v⁽²⁾, v⁽³⁾, v⁽⁴⁾and v⁽⁵⁾are considered (see Table 6).

[0071] The fourth candidate v⁽⁴⁾corresponds to the first index range having a non-zero upper limit. Therefore, the fourth candidate v⁽⁴⁾is selected as the third column e₃for the 4×4 balanced array E(10) corresponding to the message u=10.

[0072] Thus, after the third iteration, $E\left(10\right)=\begin{array}{cccc}0& 0& 1& e_{1,4}\\ 1& 1& 0& e_{2,4}\\ 1& 0& 0& e_{3,4}\\ 0& 1& 1& e_{4,4}\end{array}$

[0073] The updated intermediate message u′ is int(0−0)=0, the index j is incremented to 4, the intermediate row type w′ is updated to w′=(2,0,1,1)−(1,0,0,1)=(1,0,1,0), and another iteration is performed. Since j=m=4, the last column e₄of the 4×4 balanced array E(10) becomes:

[0074] e₄=w′=(1,0,1,0).

[0075] Thus, $E\left(10\right)=\begin{array}{cccc}0& 0& 1& 1\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\end{array}$

[0076] In this manner, the message u=10 is encoded into a 4×4 balanced array E(10). The drive 10 would be configured to write that balanced array E(10) to the optical disc 12.

[0077] It would appear that a lookup table could be used to encode each 4-bit message into a 4×4 balanced array. Memory requirements for storing sixteen 4×4 balanced arrays would appear to be quite manageable. For two-dimensional encoding of long messages, however, the lookup table would become too large to be practical. Therefore, the above computations would be performed in order to reduce memory requirements.

[0078] FIG. 4 shows a column-wise method for decoding a balanced array E(u) into a message u. Decoding is performed essentially by reversing the encoding steps shown in FIG. 3. Given a constrained array E=[e₁,e₂, . . . , e_m] where e_jdenotes the columns of the array E, the decoding may be performed as follows. The intermediate message u′ is initialized to 0 and the intermediate row type w′ is initialized to w, the row type of E (block 302). Starting with column e₁, for each column e_j, the intermediate message u′ is updated to u′=ceiling(u′+σ_L(e_j))=┌u′+σ_L(e_j)┐ where the function σ_L(y) was defined in equation (4) (block 304). This function gives a lower bound on the number of constrained arrays with initial j−1 columns e₁, . . . , e_j−1and a j^thcolumn appearing before e_jin the predetermined ordering. As above, the row type variable w′ is updated to w′=w′−e_j, after the j^thcolumn is processed (block 306). After all m columns have been processed (block 308), the decoded message u is set to the final value of u′ (block 310).

[0079] The two-dimensional encoding can be carried out in a faster, more computationally efficient manner by performing a bit-wise encoding method instead of the column-wise encoding method described above. The bit-wise encoding method also uses the lexicographic ordering of candidates in which v⁽ⁱ⁾<v^(j)if and only if v⁽ⁱ⁾is 0 and v^(j)is 1 in the first position from the left in which they differ. However, instead of checking each candidate until the index range containing the message is found, the candidate corresponding to the range containing the message (that is, the maximal y belonging to the set of column candidates V satisfying (σ_L(y)≦u) is determined in a sequential fashion, one bit at a time.

[0080] This bit-wise method uses lower bounds on the number of arrays satisfying the constraint and having previously selected columns e₁, . . . , e_i−1and having e_j,1, . . . , e_j,kas the first k entries for the j^thcolumn. Let μ_i,k(e_j,1, . . . , e_j,k) denote this lower bound with the additional dependence on the previous j−1 columns e₁, . . . , e_i−1being implied. Equation (6) below shows how the lower bound μ_i,k(e_j,1, . . , e_j,k) is related to the lower bound of equation (4) used in the column-wise encoding procedure. Based on this relationship, for the lexicographic ordering of candidates and for any binary vector y, these lower bounds satisfy ${\sigma }_L\left(y\right)=\sum _{k\text{:}{y}_k=1}{\mu }_{j,k}\left(y_1,\dots ,y_{k-1},0\right),$

[0081] where σ_L(y) is the lower index range limit from the column-wise encoding procedure, as defined in equation (5) above and y₁,y₂, . . . , y_nare the components of y. That is, a lower bound on the number of balanced arrays starting with columns e₁, . . . , e_i−1and having a j^thcolumn e_jsmaller than y in the lexicographic ordering is given by the sum of the μ_j,k(y₁, . . . , y_k−1,0) for those k where y_k=1. This formula can then be used to determine the j^thcolumn e_jof the balanced array E(u), which, from above, is the maximal candidate y (according to the lexicographic ordering) in the set V satisfying σ_L(y))≦u′, in a bit-wise fashion in n steps.

[0082] Reference is now made to FIG. 5, which illustrates a bit-wise method of encoding a message u into a corresponding balanced array E(u). The column index j is initialized to j=1, the intermediate message is initialized to u′=u and the intermediate row type w′ is initialized to w′=w (block 402). A bit index k is initialized to k=1; the j^thcolumn e_jof the balanced array E(u) is initialized to e_j=(0,0, . . . , 0); and an intermediate lower limit σ′_Lis initialized to 0 (block 404).

[0083] The bits in the j^thcolumn e_jare determined sequentially. For each bit e_j,kbeing determined, the lower bound μ_j,k(e_j,1, . . . , e_j,k−1,0) based on the j^thcolumn elements previously selected (i.e., e_j,1to e_j,k−1) and the previous j−1 columns e₁to e_j−1is determined (block 406).

[0084] Then the intermediate lower limit σ′_Land the lower bound μ_j,k(e_j, . . . , e_j,k−1,0) are summed together (block 406) and compared to the intermediate message. If the sum of the lower limit σ′_Land the lower bound μ_j,k(e_j,1, . . . , e_j,k−1,0) is less than or equal to the intermediate message u′ (block 408), then the k^thbit e_j,kof the j^thcolumn e_jis set to e_j,k=1 (block 410) and the intermediate lower limit σ′_Lis updated to σ′_L=σ′_L+μ_j,k(e_j,1, . . . , e_j,k−1,0) (block 412); otherwise the k^thbit e_j,kis left as e_j,k=0 (block 414) and σ′_Lis unchanged. Control is returned to block 406 until all n bits of the j^thcolumn e_jhave been determined (blocks 416 and 418). The intermediate lower limit σ′_L, once updated after the k^thbit is determined, actually specifies a lower bound on the number of balanced arrays with the first j−1 columns equal to the j−1 previously selected columns of E(u) and with a j^thcolumn appearing before the partially selected j^thcolumn of E(u) in the lexicographic ordering of columns.

[0085] After all n bits of the j^thcolumn e_jhave been determined, the intermediate row type w′ is updated to w′−e_j, and the intermediate message u′ is updated to u′=int(u′−σ′_L) (block 419). If additional columns of the constrained array E(u) have not yet been determined (block 420), the column index j is incremented to j=j+1 (block 422). Control is then returned to block 404, whereby the intermediate lower limit σ′_Lis reset to 0, the bit index k is set to k=1, and the next column e_j+1is determined. This is performed until all m columns of the balanced array E(u) have been determined (block 424).

[0086] An alternative formulation of the bit-wise encoding method is as follows. Suppose k−1 bits e_j,1, . . . , e_j,k−1of the j^thcolumn e_jof the balanced array E(u) have been determined. Then, if u′ is smaller than μ_j,k(e_j,1, . . . , e_j,k−1,0), e_j,kis set to 0 and otherwise e_j,kis set to 1. In a step paralleling the column-by-column technique, the intermediate message u′ is unchanged if e_j,kwas set to 0 and it is updated to u′−μ_j,k(e_j,1, . . . , e_j,k−1,0) if e_j,kwas set to 1. After the last entry e_j,nof the column e_jis determined in this fashion with the corresponding update of the intermediate message, the final intermediate message u′ is updated for the next column to int(u′). An alternative encoder which may lead to a different encoding is obtained by updating u′ according to int(u′−μ_j,k(e_j,1, . . . , e_j,k−1,0)) after each e_j,kthat is set to 1. The difference is that the int( ) operation is applied after each k instead of only after k=n. These steps can be seen as paralleling the column based technique if 0 and 1, the choices for the next entry of the current column, are identified with the column candidates, and μ_j,k(e_j,1, . . . , e_j,k−1,0) is seen to define the boundary between the index ranges of the two choices. In this bit-wise sequential approach there are only two choices 0 or 1 at each step as opposed to the exponentially many choices for each column in the column-by-column technique.

[0087] The bounds μ_j,k(e_j,1, . . . , e_j,k−1,0) may be efficiently computed as follows for the balanced array constraint. In this case, $\begin{array}{cc}{\mu }_{j,k}\left(y_1,\dots ,y_k\right)={\lambda }_n^{m-j}\sum _{z:z_i=y_i,i=1\dots k}\left|R_{m-j}\left(w^{\prime }-z\right)\right|,& \left(6\right)\end{array}$

[0088] where the sum is over all balanced binary vectors z equal to y₁, . . . , y_kin the first k components. Using the expression for |R_m−j(w′−z)| from above this can also be expressed as $\begin{array}{cc}{\mu }_{j,k}\left(y_1,\dots ,y_k\right)={\lambda }_n^{m-j}\prod _{i=1}^k\left(\begin{array}{c}m-j\\ w_i^{\prime }-y_i\end{array}\right)\sum _{z:\left|\right|z\left|\right|=n/2-\left|\right|y\left|\right|}\prod _{i=1}^{n-k}\left(\begin{array}{c}m-j\\ w_{i+k}^{\prime }-z_i\end{array}\right),& \left(7\right)\end{array}$

[0089] where the summation is over n−k dimensional binary vectors z=z₁, . . . , z_l−ksatisfying $\sum _{i=1}^{n-k}{z}_i=n/2-\sum _{i=1}^k{y}_i$

[0090] (these sums are respectively denoted by ∥z∥ and ∥y∥ in the equation) so that the n-dimensional binary vectors (y₁, . . . , y_k, z₁, . . . , Z_n−k) are balanced.

[0091] Factoring out |R_m−j+1(w′)| from the right hand side of equation (7) for μ_j,k(y₁, . . . , y_k) gives the simpler expression $\begin{array}{cc}{\mu }_{j,k}\left(y_1,\dots ,y_k\right)={\lambda }_n^{m-j}\left|R_{m-j+1}\left(w^{\prime }\right)\right|\prod _{i=1}^k{p_i^{y_i}\left(1-p_i\right)}^{1-y_i}\sum _{z:\left|\right|z\left|\right|=n/2-\left|\right|y\left|\right|}\prod _{i=1}^{n-k}{p_{i+k}^{z_i}\left(1-p_{i+k}\right)}^{1-z_i},& \left(8\right)\end{array}$

[0092] where p_iis equal to w′_i/(m−j+1). Thus, the value μ_j,k(y₁, . . . , y_k) can be written as the product of four terms: ${\lambda }_m^{m-1},\left|R_{m-j+1}\left(w^{\prime }\right)\right|,\prod _{i=1}^k{p}_i^{y_i}{\left(1-p_i\right)}^{1-y_i},$

[0093] and $\sum _{z:\left|\right|z\left|\right|=n/2-\left|\right|y\left|\right|}\prod _{i=1}^{n-k}{p_{i+k}^{z_i}\left(1-p_{i+k}\right)}^{1-z_i}.$

[0094] The first three terms can be computed efficiently directly from their definitions while the fourth term is equal to the coefficient of x^{n/2−∥y∥} in the polynomial $P_{j,k}\left(x\right)=\prod _{i=1}^{n-k}\left[1-p_{i+k}+{\mathrm{xp}}_{i+k}\right].$

[0095] The coefficient of x^hin this polynomial will be denoted by S_j,k,h. Thus the fourth term is equal to S_{j,k,(n/2−∥y∥)}.

[0096] An example will now be provided in conjunction with the above encoding of the message u=10 into a corresponding 4×4 balanced array E(10). The column index j is initialized to j=1, the intermediate message u′ is initialized to 10, the intermediate row type w′ is initialized to (2,2,2,2), and the first column e₁of the corresponding balanced array E(10) is determined as follows.

[0097] First, the bit variable k is initialized to k=1, and the first column e₁of the array E(u) is initialized to e₁=(0,0,0,0). The intermediate lower bound σ′_Lis initialized to 0.

[0098] Then μ_1,1(0) is determined. Since w′=w=(2,2,2,2), p₁=2/(4)=½. Also n/2−∥0∥=4/2−0=2. Then, from equation (8), μ_1,1(0) is equal to μ_1,1(0)=λ₄³|R₄(2,2,2,2)|(½)S_1,1,2. The quantity λ₄was already determined to be ⅜ and R₄(2,2,2,2) was determined to be 64. The term S_1,1,2is computed by determining the coefficient of x²in the polynomial P_1,1(x)=(1−p₂+xp₂)(1−p₃+xp₃)(1−p₄+xp₄)=(½+x/2)³. The polynomial P_1,1(x) is equal to ⅛(1+x)(1+2x+x²)=⅛(1+3x+3x²+x³). Thus S_1,1,2=⅜, and therefore μ_1,1(0)=(⅜)³6⁴(½)(⅜)=(⅜)³(243) which is about 12.8. Since σ′_L+12.8>10, e,_1,1(that is, the first entry of the candidate column) is left unchanged at 0.

[0099] The variable k is incremented to k=2 and the next step is performed to determine μ_1,2(0,0). The quantity n/2−∥0,∥0 is still equal to 2. Again from equation (8), μ_1,2(0,0) is set to μ_1,2(00)=λ₄³|R₄(2,2,2,2)|(½)(½)S_1,2,2is the coefficient of x²in the polynomial P_1,2(x)=(½+x/2)². The polynomial P_1,2(x) is equal to ¼(1+2x+x²). Thus S_1,2,2is equal to ¼, and μ_1,2(0,0)=(⅜)³6⁴(½)²(¼)=(⅜)³(81) which is about 4.3. Since σ′_L+4.3=4.3≦10, the second entry e_1,2of the first column is changed to e_1,2=1, and σ_Lis now 4.3.

[0100] The variable k is incremented to 3 and the next step is to determine μ_1,3(0,1,0). This time n/2−∥0,1,0∥ is equal to 1 since ∥0,1,0∥=1. Again from equation (8), μ1,3(0,1,0) is equal to μ_1,3(0,1,0)=λ₄³|R₄(2,2,2,2)|(½)³S_1,3,1, where this time S_1,3,1is the coefficient of x in the polynomial P_1,3(x)=(½+x/2). Thus S_1,3,1is equal to ½ and μ_1,3(0,1,0)=(⅜)³6⁴(½)³(½)=(⅜)³(81) which again is about 4.3. Since σ′_L+4.3=8.6≦10, the third element e_1,3of the first column is changed to e_1,3=1, and σ′_Lis now 8.6.

[0101] The variable k is incremented to k=4 and the final step is to determine μ_1,4(0,1,1,0). This time n/2−∥0,1,1,0∥=0. From equation (8), μ_1,4(0,1,1,0) is equal to μ_1,4(0,1,1,0)=λ₄³|R₄(2,2,2,2)|(½)⁴S_1,4,0where S_1,4,0is the coefficient of x⁰or the constant term of the polynomial P_1,4(x)=1. Thus S_1,4,0is equal to 1 and μ_1,4(0,1,1,0)=(⅜)³6⁴(½)⁴=(⅜)³(81) which again is about 4.3. Since σ′_L+4.3=12.9>10, the fourth element y₄of the candidate y is left unchanged at y₄=0 (as is expected, since 0,1,1,1 would not be a balanced column), and σ′_Lremains about 8.6.

[0102] Thus the first column e₁of the balanced array E(10) was determined in a bit-wise fashion to be e₁=(0,1,1,0), precisely the same value obtained by the column-wise method. Before the second column e₂of the balanced array E(10) is determined in the same bit-wise manner, the column index j is incremented to j=2, the intermediate row type w′ is updated to w′=w′−e₁, and the intermediate message u′ is updated to u′=int(10−σ′_L)=1. The bit-wise procedure is then repeated with the new variables for the second column e₂, and so on until all of the other columns e₃and e₄of the balanced array E(10) have been determined.

[0103] Both the column-wise and bit-wise encoding procedures (and the specified variations) described above are one-to-one (and hence decodable) in the sense that any two distinct messages u₁≠u₂in the range determined during initialization are encoded into distinct balanced arrays E(u₁)≠E(u₂). It is a non-trivial property of the lower bounds on the cardinalities of sets of balanced arrays with partially specified entries that are used in each iteration, that the resulting encoding is one-to-one. If instead of lower bounds, the exact cardinalities were used, the decodability would follow from the classical enumerative coding technique, upon which the above techniques are based. In the case of the balanced array constraint, however, the applicants are not aware of an efficient technique for computing the exact cardinalities involved. Therefore a direct application of the classical enumerative coding technique is believed to be impractical. A key aspect of the present invention is the fact that the exact cardinalities in the classical enumerative coding technique can be replaced by the above polynomial-time computable (as demonstrated by the bit-wise technique) lower bounds, and still obtain a one-to-one encoding with very low redundancy. This point also applies to the computational complexity of decoding, as described below.

[0104] FIG. 6 shows a method for the bit-wise decoding of a balanced array into a message. Decoding is performed essentially by reversing the encoding steps shown in FIG. 5. The constrained array E is processed one column at a time, starting with the first column and updating the intermediate variables u′ and w′ after each column. The decoded message u is set to the final value of u′ obtained after the last column of E has been processed.

[0105] The decoding is performed as follows. The intermediate message variable u′ is initialized to 0, the intermediate row type variable w′ is initialized to w, and j the column index j is initialized to j=1 (block 502). Assume j−1 columns have already been processed and σ′_Lis initialized to 0 at the start of the processing of the j^thcolumn (block 504). Each entry e_j,kof the j^thcolumn is examined starting with the first entry (k=1) and if e_j,k=1 (block 506), the intermediate variable (σ′_Lis updated to σ′_L=σ′_L+μ_j,k(e_j,1, . . . , e_j,k−1,0) (block 508). If e_j,k=0, the intermediate variable σ′_Lis left unchanged. After the last entry (k=n) of the j^thcolumn has been processed in this fashion (blocks 510 and 512), the intermediate message u′ is updated as u′=u′+ceiling(σ′_L) and the intermediate row type w′ is updated to w′=w′−e_j(block 514). In preparation for the next column (block 516), the column index j is incremented by 1 (block 518) and control is returned to block 504, whereby σ′_Lis reset to 0, and k is reset to k=1. After the last column has been processed (block 516), the decoded message u is set to the intermediate message u′ (block 520).

[0106] In an alternative implementation σ′_Lcan be replaced by u′ in the above operations and the corresponding final updating of u′ at the end of each column can be replaced by u′=ceiling(u′). If, during encoding u′ is updated to int(u′−μ_j,k(e_j,1, . . . , e_j,k−1,0)) each time e_j,kwas set to 1, the corresponding alternative decoder would update u′ to u′+ceiling(μ_j,k(e_j,1, . . . , e_j,k−1,0)) for each k where the column entry e_j,kis 1. For this alternative encoder/decoder pair (which, as noted above, may yield a different mapping between messages and constrained arrays) the intermediate message u′ is always an integer and the intermediate lower limit σ′_Lis not needed.

[0107] FIGS. 7(a) and 7(b) show two possible hardware implementations 600 and 700 for the encoding and decoding methods described above. FIG. 7(a) shows an implementation 600 including an application specific integrated circuit (“ASIC”) 602 and off-chip memory 604 for performing the encoding or decoding in accordance with either the bit-wise or column-wise method above. FIG. 7bshows a microprocessor 702 and memory 704 (e.g., collectively long-term memory such as a hard drive and short-term memory such as DRAM) for storing a program 706. The program 706 instructs the microprocessor 702 to perform the encoding or decoding in accordance with either the bit-wise or column-wise method above. The microprocessor 702 and memory 704 could be part of a machine such as a personal computer or workstation.

[0108] Thus disclosed is an encoder that encodes messages into n×m constrained arrays, and a decoder that decodes n×m constrained arrays into messages. The constrained arrays may be balanced and, therefore, dc free. Redundancy of encoding is lower than previously reported. As a consequence of reducing the redundancy, a higher density of messages can be packed into an n×m array. This, in turn, allows the size of the balanced array to be reduced which, in turn, allows more data to be stored on a recordable medium.

[0109] Enumerative coding techniques may be used to ease computational and memory requirements. At each iteration of encoding, a range of available arrays is determined. There is no need to determine the exact number of balanced arrays. This is especially valuable for the coding of large messages. The use of a polynomial equation to find the lower limit of the index ranges further eases the computational requirements and increases computational speed. Moreover, the encoding doesn't go down a trail that runs out of arrays.

[0110] Although the invention was described above in connection with a drive that writes to a recordable medium such as an optical disk, it is not so limited. The invention could be applied to other devices including, but not limited to, hard drives and holographic storage devices. Moreover, the invention could be applied to other types of recordable media, such as read-only media.

[0111] The invention is not limited to the specific embodiments described and illustrated above. For example, the coding method is not limited to balanced arrays (i.e., even numbers of 1's and 0's). The vector w can specify row types having any desired number of 1's in the rows. Non-integer indices may be used instead of integer indices. The terms rows and columns may be used interchangeably through transposition. A minimal candidate y that satisfies σ_L(y)≦u could be used instead of the maximal candidate y.

[0112] Accordingly, the invention is not limited to the specific embodiments described and illustrated above. Instead, the invention is construed according to the claims that follow.