Patent Description:
In a modern memory, the directly adjacent data stored on the recording medium will cause intersymbol interference due to mutual influence. In order to reduce the possibility of data errors and improve the reliability of the memory system, data recording on the storage medium usually needs to meet certain restrictions, that is, the data needs to be encoded into some patterns that meet special constraints and restrictions before it can be stored on the recording medium. Constraint patterns vary with different applications. The common constraint types comprise a maximum transition run constraint (MTR), a run-length limitation constraint and other constraints.

Data access along one-dimensional tracks of the recording medium is a common storage technology at present. In recent years, with increasing demand and technological progress, the next-generation data storage technology that accesses data in two-dimensional pages (or even three-dimensional) has been significantly developed for the purpose of increasing data transmission rate and storage capacity. Related examples comprise a phase change memory (PCM), a holographic memory, a two-dimensional optical disc, a two-dimensional patterned media recording, etc. In the above-mentioned storage technology, the data is arranged and combined into a two-dimensional data array in a quadrilateral grid or hexagonal grid on a two-dimensional plane, and the intersymbol interference becomes more complex and has changed from a one-dimensional situation to a two-dimensional situation. In addition to consider the mutual influence of intersymbol interference on the data in the left and right directions of "horizontal", the mutual influence on adjacent data in the "vertical" direction also needs to be considered.

<CIT> discloses a two-dimensional run-length limited (RLL) (<NUM>,<NUM>) code method and apparatus. The encoding/decoding method and device can solve problems that any binary two-dimensional data array composed of <NUM>'s and <NUM>'s satisfies two-dimensional (<NUM>,<NUM>) RLL constraints in both horizontal and vertical directions.

In some specific applications, in order to avoid the direct influence between the data "<NUM>", it is required that the data "<NUM>" cannot be directly adjacent to each other in four directions in the two-dimensional data array, which is commonly referred to as a two-dimensional square constraint. Specifically, taking the quadrilateral grid as an example, the two-dimensional square constraint means that in the two-dimensional data array composed of data "<NUM>" and data "<NUM>", the two data "<NUM>" cannot be directly adjacent in the horizontal direction, the vertical direction, the northeast direction and the southeast direction. That is to say, in the binary data pattern recorded on the storage medium, the pattern combination shown in <FIG> cannot appear.

In the above-mentioned two-dimensional square constraint, in the storage technology that accesses data along one-dimensional tracks (such as optical recording and magnetic recording), in the recorded data sequence, any two data "<NUM>" cannot be directly adjacent. Traditionally, a solution to this problem is to adopt a one-dimensional run-length limited (<NUM>,∞) (RLL) encoding method. However, in the above-mentioned data accessing technology according to two-dimensional pages, the limitation of the direct neighbor constraint between the data "<NUM>" is reflected in <NUM> directions, and the one-dimensional (<NUM>,∞) RLL encoding method that can only solve the horizontal direction is obviously powerless here.

In view of the defects in the prior art, the purpose of the present invention is to provide a two-dimensional square constraint encoding and decoding method and device based on a quadrilateral grid, so that in a binary data array composed of data "<NUM>" and "<NUM>", along the four directions of horizontal, vertical, northeast, and southeast, data "<NUM>" cannot be directly adjacent to each other.

The problem is solved by a two-dimensional square constraint encoding method according to claim <NUM>, a two-dimensional square constraint decoding method according to claim <NUM>, a two-dimensional square constraint encoding method according to claim <NUM>, and a two-dimensional square constraint decoding method according to claim <NUM>. Preferred embodiments are described in the dependent claims.

The above-mentioned technical solutions have the following beneficial effects.

In order to make the purposes, technical solutions and advantages of the present invention clearer, the present invention will be further described below in detail with reference to the drawings in combination with the embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, but not to limit the scope of the present invention. In addition, the technical features involved in the various embodiments of the present invention described below can be combined with each other.

An embodiment provides a two-dimensional square constraint encoding and decoding method, which comprises an encoding method and a decoding method, and the encoding method comprises:.

As shown in <FIG>, the two-dimensional codeword adopted in the embodiment is a two-dimensional array with <NUM> bits high and <NUM> bits long, which is the smallest access unit in the process of actually accessing two-dimensional data.

In the specific encoding process, the timing relationship between the read <NUM>-bit data is shown in <FIG>, wherein ti+<NUM> represents the next time of the data, ti represents the current time of the data, and ti-<NUM> represents the previous time. As shown in <FIG>, when the encoder needs to encode the <NUM>-bit data input at time ti, the encoder performs two-dimensional encoding according to the one-dimensional <NUM>-bit data and the next set of input <NUM>-bit data (look-ahead data), and the current state of the encoder, and then outputs the encoded two-dimensional codeword. On the other hand, the next state of the encoder (i.e. the output state) is updated in real time according to Table <NUM> (or Table <NUM>), based on the current state of the encoder, the current input one-dimensional <NUM>-bit data and the next set of input one-dimensional <NUM>-bit data (look-ahead data). The next state after the update is taken as the current state of the encoder at time ti+<NUM>.

after constructing a two-dimensional constraint array with a size equal to one page from all the two-dimensional codewords in a specified order, outputting the two-dimensional constraint array to a two-dimensional data recording device.

As shown in <FIG>, it is a layout diagram of the two-dimensional codeword in the data array. The layout diagram illustrates that when one-dimensional user data is written in a two-dimensional array method, from the perspective of the smallest access unit of a <NUM>*<NUM> two-dimensional array, the data is cascaded in a row-by-row manner from left to right and from top to bottom.

The decoding method in the present embodiment comprises:
reading the two-dimensional constraint array from the two-dimensional data recording device, and dividing the two-dimensional constraint array into several <NUM>*<NUM> two-dimensional codewords in a specified cascading order, that is, dividing according to the minimum access unit. In the embodiment, as shown in <FIG>, the division is performed row by row from left to right and from top to bottom.

As shown in <FIG>, the decoder decodes the two-dimensional codeword in sequence by way of sliding-block decoding. By taking advantage of the decoding table of the two-dimensional square constraint decoder and in combination with the current two-dimensional codeword and the next two-dimensional codeword, the decoder decodes each two-dimensional codeword into the one-dimensional <NUM>-bit data in sequence, and successively assembles all the one-dimensional <NUM>-bit data obtained by decoding into a one-dimensional data stream and outputs the one-dimensional data stream.

In the above encoding method, a basic two-dimensional codeword or an alternative codeword needs to be used to encode the <NUM>-bit data. The one-dimensional <NUM>-bit data comprises <NUM>, <NUM>, <NUM>, and <NUM>. In this embodiment, Table <NUM> is a basic code table.

On the basic of Table <NUM>, the above-mentioned one-dimensional <NUM>-bit data can be encoded into a <NUM>*<NUM> two-dimensional codeword, and the above four <NUM>*<NUM> two-dimensional codewords can be horizontally cascaded in pairs to form sixteen types of <NUM>*<NUM> two-dimensional arrays, of which four situations violate the two-dimensional square constraint limitation, namely:
<IMG>
When table <NUM> is taken to encode the data, the four counter examples are replaced with the corresponding codeword combination in the substitute code table <NUM> if the above situations occur.

According to the above Tables <NUM> and <NUM>, the encoding table <NUM> can be constructed and the encoder can perform encoding by looking up Table <NUM>.

According to Table <NUM>, the decoding table <NUM> of the decoder can be constructed for the decoder to perform decoding. The X in Table <NUM> indicates non-emergence.

It should be pointed out that: in the above Table <NUM>, when keeping <NUM> sets of one-dimensional <NUM>-bit data and four <NUM>*<NUM> two-dimensional codewords unchanged, the correspondence between each set of one-dimensional <NUM>-bit data and four <NUM>*<NUM> two-dimensional codewords can be changed. Through simple calculations, there are as many as <NUM> such correspondences. In other words, the correspondence specified in Table <NUM> is only one of these <NUM> correspondences, but once the corresponding relationship between the two is determined, the new basic code table and the new substitute code table that are consistent with the correspondence can be uniquely obtained, and the forms thereof are the same as the basic code table <NUM> and the substitute code table <NUM>. The basic code table and the substitute code table generated based on this new correspondence will also generate a corresponding unique new encoding table and new decoding table, but the form of the tables is the same as that of the above table <NUM> and table <NUM>, and the principle is exactly the same.

In the present invention, the second embodiment of the basic code table and the substitute code table is also provided. In the second embodiment, the basic code table is shown in Table <NUM>.

In the second embodiment, when Table <NUM> is taken to encode the data, the four counter examples are replaced with the corresponding codeword combination in the substitute code table <NUM> if the four violations of the two-dimensional square constraint limitation occur.

Similarly, according to the above table <NUM> and table <NUM>, the encoding table <NUM> can be constructed, and the encoder can perform encoding by looking up Table <NUM>.

In the second embodiment, the decoding table <NUM> of the decoder can be constructed according to Table <NUM> for the decoder to perform the decoding. The X in Table <NUM> indicates non-emergence.

On the basis of the above embodiments, the present invention further provides an encoding and decoding device suitable for the above embodiments, comprising an encoding device, a decoding device and a two-dimensional data recording device.

As shown in <FIG>, the encoding device comprises a one-dimensional data stream caching component, a data stream dividing component, a square constraint codeword encoder, and a two-dimensional data array assembling component that are successively connected.

The one-dimensional data stream caching component, which is configured to cache a one-dimensional data stream according to a code rate and the size of a two-dimensional data page.

The data stream dividing component, which is configured to divide the one-dimensional data stream cached by the one-dimensional data stream caching component into several sets of one-dimensional <NUM>-bit data.

The square constraint codeword encoder, which is configured to read several one-dimensional <NUM>-bit data required to complete the encoding from the data stream dividing component, encode each set of <NUM>-bit data into a <NUM>*<NUM> two-dimensional codeword in sequence according to an encoding table of the encoder, and update the current state the encoder in real time.

The two-dimensional data array assembling component, which is configured to cache all two-dimensional codewords generated by the square constraint codeword encoder, and construct a two-dimensional constraint array with a size equal to one page according to the encoding sequence; further configured to output the two-dimensional data of the page constructed to the two-dimensional data recording device. The above encoding sequence is "from left to right, top to bottom".

As shown in <FIG>, the decoding device comprises a two-dimensional data array caching component, a two-dimensional codeword dividing component, a square constraint codeword decoder, and a one-dimensional data stream assembly component that are successively connected.

The two-dimensional data array caching component, which is configured to cache a two-dimensional constraint array of a page output by the two-dimensional data recording device.

The two-dimensional codeword dividing component, which is configured to divide the two-dimensional constraint array into several <NUM>*<NUM> two-dimensional codewords in a specified order, and input the two-dimensional codewords into the square constraint codeword decoder in the order of sequence, and the above specified order is "from left to right, top to bottom".

The square constraint codeword decoder, which is configured to decode each two-dimensional codeword into a set of one-dimensional <NUM>-bit data in sequence according to the principle of sliding-block decoding and by taking advantage of the decoding table and in combination with the current two-dimensional codeword, the previous two-dimensional codeword and the next two-dimensional codeword.

The one-dimensional data stream assembling component, which is configured to successively assemble all the one-dimensional <NUM>-bit data output by the square constraint codeword decoder into the one-dimensional data stream for output.

As shown in <FIG>, based on the second embodiment (i.e. Table <NUM>) of the above encoding and decoding device and the encoding table, the encoding process of the two-dimensional square constraint array is given. Assuming that the size of a two-dimensional data page is <NUM>*<NUM>, the one-dimensional random data sequence input to the encoder is <NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM> (input from left to right), and the initial state of the encoder is the first state (if the initial state is the second state, the analysis is similar). At time ti, the current input data of the encoder is <NUM>, and the next data (look-ahead data) is <NUM>. The encoding is performed according to Table <NUM>. The encoding of the one-dimensional <NUM>-bit data <NUM> is as follows:
<IMG>
and the next state of the encoder is the first state (i.e. unchanged). At time ti+<NUM>, the current input data of the encoder is <NUM>, the next data (look-ahead data) is <NUM>, and the current state of the encoder is <NUM>, so the encoding of the current one-dimensional <NUM>-bit data <NUM> is as follows:
<IMG>
and the next state of the encoder becomes the second state. At time ti+<NUM>, the current input data of the encoder is <NUM>, and the current state of the encoder is the second state. According to Table <NUM>, the encoding of the current one-dimensional <NUM>-bit data <NUM> is as follows:
<IMG>
and the next state of the encoder becomes the first state. Repeating the above-mentioned process so as to achieve the encoding of the one-dimensional random data sequence. In the embodiment, the encoding of the subsequent data is as follows:
<IMG>
<IMG>
During the entire encoding process, the state of the encoder changes to: <NUM>. The encoded data is stored in the two-dimensional data recording device.

As shown in <FIG>, the corresponding decoding process is given according to the above-mentioned encoding process. First, the two-dimensional data array is read from the two-dimensional data recording device, and then divided into several the following two-dimensional data sub-arrays according to a set of <NUM>*<NUM>.

According to the writing order of the codewords in the two-dimensional array, the two-dimensional data sub-arrays obtained above are input to the decoder in sequence for decoding by taking the <NUM>*<NUM> two-dimensional codewords as the basic unit. At time ti, the current <NUM> two-dimensional codeword that needs to be decoded by the decoder is <NUM>, <NUM> because the next two-dimensional codeword of the data in the <NUM> two-dimensional array is <NUM>, according to Table <NUM>, the decoding of the <NUM> data does not require the information of the previous two-dimensional codeword, so the decoding is as follows:
<IMG>
At time ti+<NUM>, the next two-dimensional codeword of the current <NUM><NUM> two-dimensional codeword <NUM> is <NUM>, so the current data at time ti+<NUM> <NUM><NUM> should be decoded as <NUM>, that is, the decoding is as follows:
<IMG>
Repeating the above process so as to realize the decoding of the two-dimensional data array, and the decoding of the remaining two-dimensional codewords is as follows:
<IMG>.

Finally, "<NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM><NUM>" is assembled into a one-dimensional user data stream <NUM> (from right to left) according to the generation sequence and output, so that the decoder can decode a page of the two-dimensional data array.

In the above embodiment, the encoder in the encoding device uses a look-ahead data encoding method, that is, the data encoding output is not only directly related to the current data, but also related to the next data and the current state of the encoder. On the other hand, in the decoding stage, in order to decode correctly, the decoder adopts a sliding-block decoding method to decode the current two-dimensional codeword. In short, the decoding output of the two-dimensional codeword is directly related to the current codeword, the previous two-dimensional codeword, and the next two-dimensional codeword. This sliding-block decoding method makes full use of the chronological constraint information between the codewords. Therefore, there is a decoding window for decoding. The size of the decoding window has a significant impact on the catastrophic propagation of decoding errors. However, in the embodiment, although the decoding window is theoretically three codewords, there are only two codewords in fact, so the decoding error does not exceed two data words at most, that is, <NUM>-bit data, which is very advantageous in practical applications.

Claim 1:
A two-dimensional square constraint encoding method, the constraint being that "<NUM>"s are not directly adjacent to each other along four directions of a horizontal direction, a vertical direction, a northeast direction and a southeast direction of the two-dimensional constraint array, the method being used on systems wherein data is recorded and accessed as two-dimensional pages, wherein:
the encoding method comprises: caching a one-dimensional data stream, and dividing the one-dimensional data stream into several sets of one-dimensional <NUM>-bit data; through looking up an encoding table of a two-dimensional square constraint encoder, encoding each set of <NUM>-bit data into a <NUM>*<NUM> two-dimensional codeword in sequence, and constructing all the two-dimensional codewords obtained by encoding into a two-dimensional constraint array with a size equal to one page in an encoding sequence;
the one-dimensional <NUM>-bit data are respectively <NUM>, <NUM>, <NUM> and <NUM>, basic two-dimensional codewords are respectively
<IMG>
wherein the one-dimensional <NUM>-bit data of <NUM>, <NUM>, <NUM> and <NUM> respectively correspond to the basic two-dimensional codewords of
<IMG>
if the current <NUM>-bit data and the next set of <NUM>-bit data show four conditions as <NUM>, <NUM>, <NUM> and <NUM>, the basic two-dimensional codeword combinations corresponding to the current <NUM>-bit data and the next set of <NUM>-bit data should be respectively replaced with the following combinations:
<IMG>