带保护字的二维游程长度受限约束的编解码器及使用方法

摘要

本发明提供了一种带保护字的二维游程长度受限约束的编解码器及其使用方法，该编解码器包括编码器和解码器，所述编码器包括：数据缓冲及分组模块、二维码字生成模块、二维字单元页构造模块、二维码字写入阵列模块、保护字填充模块，上述五个模块依次连接，最后通过其中的保护字填充模块输出给二维数据记录装置；所述解码器包括：二维数据缓冲模块、二维字单元页构造模块、一维数据字译码模块、一维数据流组装模块，上述五个模块依次连接，最后通过其中的一维数据流组装模块输出。本发明的编解码方法和装置能解决由“0”和“1”构成的二维数据阵列在两个方向上均满足(1，3)RLL约束的二维(1，3)RLL的技术问题。

说明书

技术领域

本发明属于数据存储领域和通信领域。具体涉及当将二进制数据存储在矩形格子组成的 平面上，无论是在水平方向还是在垂直两个方向上，在连续数据”1”之间，数据“0”的游 程长度最少等于1，最多不超过3的编解码器及使用方法。

背景技术

在现代存储技术和通信技术中，通道由于内在的物理特性，会对穿越通道的信号产生具 有某种形式的约束限制。为降低通道对信号的影响，提高存储系统和通信系统可靠性，解决 这一问题的办法之一就是用约束编码技术，约束编码又称调制编码。(d，k)游程长度受限约 束(RLL)是这类约束的一个典型代表。这里d表示在连续数据“1”之间，“0”的游程长度 最小值，k表示其最大值。著名的Miller码，即改进型调频码MFM(美国专利号3,108,261， 公布日1963年10月22日)，就是其中的一个代表。在MFM码中，相邻数据“1”之间，“0” 的游程长度至少等于1，最多不超过3，因此MFM码有时候又称为一维(1，3)RLL码。

随着技术的发展，近些年出现了将数据以二维页面方式进行存储的新型存储器，比如全 息存储器和二维光盘等。这类存储器和目前主流存储器的一个最大不同之处在于：数据每次 按照二维页面的方式存储在记录介质上，在读取数据时，也是按照整页整页的方式进行。图 1描述了在全息存储器中数据的这种二维布局示意。

在上述二维存储器中，以图1为例，若不考虑边界的影响，每位比特信息都有4个比特 信息和它本身直接相邻(即通常所说的上、下、左和右)。比较而言，在一维情形下，数据 的布局如图2所示。

从图1和图2可以看出，在二维存储中，二进制数据阵列在水平和垂直两个方向上都有 约束限制要求。这样前面提到的改进型调频码(MFM)，数据之间的内在约束条件会因空间尺 度从一维转到二维而发生相应变化，原先在一维条件下满足的约束限制在二维情形下就不再 有效。因此寻求新的二维约束编解码方法，保证数据在水平和垂直两个方向上能同时满足新 型二维存储技术的发展和需求就显得非常有必要。

发明内容

本发明所要解决的技术问题是：提供一种带保护字的二维游程长度受限约束的编解码器 及使用方法，本发明的编解码方法和装置能解决由“0”和“1”构成的二维数据阵列在两个 方向上均满足(1，3)RLL约束的二维(1，3)RLL的技术问题。

本发明所采用的技术方案是：带保护字的二维游程长度受限约束的编解码器，包括编码 器和解码器，所述编码器包括：

数据缓冲及分组模块，该模块在缓冲接收一维数据流的同时，根据二维数据页的大小， 将数据划分成若干个长度相等的分组；

二维码字生成模块，该模块根据编解码规则表，将2比特的一维数据生成2×2的二维约 束码字；

二维字单元页构造模块，该模块将二维数据页划分成若干个2×2的二维数据子阵列组成 的二维字单元页；

二维码字写入阵列模块，该模块将2×2的二维约束码字，沿着二维字单元页斜线方向的 奇数行逐行写入到二维数据阵列中；

保护字填充模块，该模块依据二维码字生成模块所选编解码规则表选取相应的二维保护 字，并沿二维字单元页斜线方向的偶数行顺序，将二维保护字逐行填入到二维数据阵列；

上述五个模块依次连接，最后通过其中的保护字填充模块输出给二维数据记录装置；

所述解码器包括：

二维数据缓冲模块，该模块暂时存放从二维数据记录装置读取的二维数据阵列；

二维字单元页构造模块，该模块将二维数据阵列划分成由2×2的二维数据子阵列为最小 读取单元的二维字单元页；

一维数据字译码模块，该模块将2×2的二维约束码字，根据相应的编解码规则表译码成 大小等于2比特的一维数据字；

一维数据流组装模块，该模块将一维数据字按照产生的先后顺序组装成一维数据流；

上述五个模块依次连接，最后通过其中的一维数据流组装模块输出。

所述的带保护字的二维游程长度受限约束的编解码器的使用方法，是通过编码器实现编 码过程，依次包括以下步骤：

S101)首先根据二维数据记录装置的存储大小，将大小为2N×2M的二维数据页以2×2 的字单元为一组，划分成包含N×M个大小相同的二维数据字单元的数据页，然后判断该数据 页中可编码的位数；

S102)数据缓冲及分组模块将输入的二进制一维数据流均匀地划分成若干一维数据字块， 每个数据字块包含数目等于一个数据页中可编码位数的数据，然后对每块中的数据按2比特 一组划分成若干一维数据字，并将数据字输入到数据缓冲区暂存；

S103)二维码字生成模块从数据缓冲区读取一个数据字块，选取编解码规则表将当前数 据字块中的所有一维2比特数据字转化成相应的2×2二维约束码字；

S104)二维字单元页构造模块将二维数据页划分成若干个以2×2的二维数据子阵列为最 小读取单元的二维字单元页，与步骤S101得到的数据页相对应；

S105)二维码字写入阵列模块将步骤S103)得到的2×2二维约束码字以步骤S104得到 的二维字单元页的字单元行为基准，沿二维字单元页斜线方向的奇数行，从右上角到左下角 依次将二维数据字写入大小等于2×2的字单元中，直至该行的字单元全部被写入为止；

S106)判断是否有下一个斜线方向的奇数行尚未写入，若有转至步骤S105；若二维字单 元页奇数行的所有字单元被写满二维数据字，则进入下一步；

S107)保护字填充模块根据步骤S103)选取的编解码规则表，选取对应的二维保护字， 沿二维字单元页斜线方向的偶数行，从右上角到左下角依次将该二维保护字填充到字单元中， 直至该行的所有字单元全部被填满为止；

S108)判断是否有下一个斜线方向的偶数行尚未填满，若有转至步骤S107；若所有偶数 行的二维字单元被填满二维保护字，进入下一步；

S109)判断是否还有未编码的一维数据字块，若有转至步骤S103；否则结束编码过程。

所述的带保护字的二维游程长度受限约束的编解码器的使用方法，是通过解码器实现解 码过程，依次包括以下步骤：

S201)将从二维数据记录装置读取的二维数据阵列暂时存放在二维数据缓冲模块中；

S202)二维字单元页构造模块读取大小为2N×2M的二进制数据阵列，将该二维数据阵列 以2×2为最小读取单元进行均匀划分，形成大小等于N×M的二维字单元页；

S203)一维数据字译码模块以该二维字单元页的字单元行为基准，沿字单元页斜线方向 的奇数行，依据编码器编码顺序，从右上角到左下角依次读取字单元数据，根据编解码表译 码出相应的一维2比特数据字；

S204)判断是否有下一个斜线方向的奇数行尚未译码，若有转至步骤S203；若二维字单 元页的奇数行所有字单元被译码，进入下一步；

S205)一维数据流组装模块将得到的一维2比特数据字按照相应的译码先后次序进行组 装，获取对应的一维二进制数据块；

S206)判断是否还有尚未解码的二维数据阵列，若有转至步骤S202；否则将上述步骤得 到的一维二进制数据块按照先后顺序合并成一维数据流输出，译码结束。

本发明的技术效果如下所述：

1)编码器是状态无关的。编码器状态数是评价编码器性能的一个重要指标。状态无关的 编码器是设计编码器的最佳选择。在本发明中，数据在编码和译码过程中，都是分块独立的， 数据无论是在编码和译码过程中，都和相邻数据无关，即编码器是状态无关的。

2)二维码字编解码规则表构造简单。在本发明中，2×2的二维约束码字和一维2比特 数据是一一对应的，通过简单的编解码规则方程，即可实现一维2比特数据到2×2的二维约 束码字的编码过程，反之，通过查找2×2阵列的特定数据比特，即可实现一维2比特数据的 译码。

3)二维保护字是和编解码规则一一对应的。在本发明中，所述二种编解码规则，分别对 应于不同的二维保护字，即对指定的编解码规则表，其所需的二维保护字是唯一的，不同的 编解码规则，对应不同的二维保护字，二者不可替代。

附图说明

图1是二维数据记录格式示意图(全息存储器)。

图2是一维数据光盘记录格式示意图。

图3是满足二维2D-(1，3)RLL约束的二维数据阵列示意图。

图4是4个方形格子构成的二维字单元。

图5是二维阵列(6×6)划分成二维字单元页(3×3)示意图。

图6是两种编码解码规则表；图6(a)表示第一种编码解码规则表；图6(b)表示第二 种编码解码规则表。

图7是二维字单元行序编号示意图。

图8是编码器原理框图。

图9是解码器原理框图。

图10是基于图6(a)编解码规则的二维阵列构造造实施例。

图11是基于图6(a)编解码规则的二维阵列译码实施例。

具体实施方式

本发明适用于将数据按照二维阵列(即页面)形式记录的数据存储系统。系统典型代表 有全息全息存储器及二维光盘等二维新型存储器。本发明的另一个发明目的是提供两种二维 游程长度受限约束的编码方法。本发明的另一个目的是提供两种二维游程长度受限约束的解 码方法。本发明的另一个目的是提供相应的编码和解码装置。

针对背景技术提出的问题，本发明给出了两种二维游程长度受限约束的编解码方法，即 采取本发明给出的编码方法，能够保证二进制数据阵列，无论是在水平还是垂直方向上，在 连续数据“1”之间，“0”的游程长度最少是1，最多不超过3的约束限制。我们将本发明给 出的这种编解码方法二维(1，3)游程长度受限约束码，记为2D-(1，3)RLL码。

基于本发明给出的方法，因存在二维保护字，所述编码器的码率等于1/4，译码器在译 码阶段不会产生错误传播，译码错误仅限于一个数据字即2bits数据，即当前数据的译码错 误不会对后继数据的译码造成影响。

为了实现本发明的目的，本发明采取的技术方案是，二维(1，3)RLL约束编码方法，包 括下述步骤：

第一步：首先将大小等于2N×2M的二维数据页以2×2为一组，划分成N×M个大小相同 的二维字单元页，然后转步骤二；

第二步：将输入的二进制数据流均匀地划分成数目等于页面大小的若干块，然后对每块 中的数据，按两两一组划分成大小等于2的若干一维数据字，每个字可以是如下4个值中的 任意一个：00，01，10，11，并将这些一维数据字输入到数据缓冲区暂存，转步骤三；

第三步：从缓冲区读取一维数据字，按照图6所示编解码规则表对当前一维数据字进行 编码并转化成2×2的二维约束码字，然后将该2×2的二维约束码字以字单元行为基准，沿 二维字单元页斜线方向的奇数行，从右上角到左下角依次将该2×2的二维约束码字写入大小 等于2×2的字单元中，转步骤四；

第四步：重复第三步，直至奇数行的所有字单元被写满2×2的二维约束码字为止；转步 骤五；

第五步：顺序沿着二维字单元页斜线方向的偶数行，从右上角到左下角，依次将和第三 步所选编解码规则表对应的二维保护字填充到字单元中，直至该行的字单元全部被填满为止；

第六步：重复第五步，直到编码结束。

解码步骤如下：

第一步：读取大小等于2N×2M的二进制数据阵列，将数据阵列按照2×2二维子阵列的 方式进行均匀划分，形成以2×2为基本读取单位，大小等于N×M的二维字单元页；

第二步：沿着N×M的二维字单元页的斜线方向，从右上角到左下角，依次读取奇数行的 二维字单元数据，根据编码过程所选的编解码规则表，译码出相应的2比特一维数据字；

第三步：重复第二步，直至二维阵列被译码完成；

第四步：将第二步得到的2比特一维数据字按照译码的先后次序进行组装，产生相应的 一维二进制数据块，转步骤五；

第五步：判断是否输入下一个2N×2M的二维数据阵列，若是转步骤一；否则将上述步骤 得到的一维二进制数据块按照先后顺序合并成一维数据流并输出，译码结束。

为了实现本发明的目的，本发明还提供了实现上述数据编码方法的编码器，包括：

数据缓冲及分组模块，该模块在缓冲一维数据流的同时，根据二维阵列的大小，将数据 划分成若干个长度相等的一维数据分组；

二维码字生成模块，该模块根据图6描述的编解码规则表，生成相应的二维约束码字， 并输入到二维字单元模块；

二维字单元页构造模块，该模块将二维数据页划分成若干个2×2的二维数据子阵列组成 的二维字单元页；

二维码字写入阵列模块，该模块将2×2的二维约束码字，沿着二维字单元页斜线方向的 奇数行逐行写入到二维数据阵列中；

保护字填充模块，该模块依据图6编解码规则表，依据上述二维码字生成模块所选编解 码规则，选取相应的保护字，沿着二维字单元页斜线方向，如图7所示二维字单元页的偶数 行顺序，从右上角到左下角，将二维保护字逐行填入到2N×2M的二维数据阵列。

为了实现本发明的目的，本发明还提供了实现上述数据解码方法的编码器，包括：

二维数据缓冲模块，该模块主要用于暂时存放从二维数据记录装置读取的二维数据阵列；

二维字单元页构造模块，该模块主要用于将2N×2M的二维数据阵列划分成由2×2为最 小读取单元的N×M的二维字单元页；

一维数据字译码模块，该模块主要用于将2×2的二维字单元，根据相应的编解码规则表， 译码成大小等于2比特的一维数据字；

一维数据流组装模块，该模块主要用于将大小等于2比特的一维数字按照产生的先后顺 序组装成一维数据流。

总之，本发明能将一维数据流转化成满足参数指定的游程长度受限的二维数据阵列。所 述二维游程长度受限约束编码方法包括将输入数据进行分割成特定大小的分组；然后按照对 应的编码规则将2比特的一维数据字转化成2×2的二维约束码字；最后将生成的2×2的二 维约束码字和相应的二维保护字根据预先指定方法进行写入，最终达到上述由数据“0”和“1” 构成的二维数据阵列在水平和垂直两个方向上都满足约束条件，即数据“0”的游程长度无论 是在水平还是在垂直方向上，都满足最小为1，最多等于3的要求。本发明设计了两种编解 码规则及其对应的编解码器，两种编码器的码率均等于1/4。本发明给出的编解码器是状态 无关的编码器，因此不会因译码错误而导致误码的灾难性传播，即当前数据译码错误不会对 后继数据的译码造成任何负面影响，译码错误仅局限于当前2比特数据。

下面结合附图和实施例对本发明作进一步的详细说明：

如图3所示，描述本发明产生的二维数据阵列，该阵列无论是在水平方向还是在垂直方 向上，在相邻数据“1”之间，数据“0”的游程长度都满足最小等于1，最多不超过3的约 束条件。

如图4所示，由2×2个方形格子构造的二维字单元，是编解码二维阵列的基本单位数据。

如图5所示，将大小等于6×6的二维阵列，转化为大小等于3×3的二维字单元页，用 这种方式可完成将一维数据流写入到满足2D-(1，3)RLL约束限制的二维数据阵列中。

如图6所示，图6(a)给出的是第一种编解码规则表以及相应的保护字，在该编解码规 则中，00，01，10和11这四个数据分别用大小等于2×2的二维约束码字来代替，同时在编码 过程中，为了满足相应的约束限制，需要一个特殊的二维阵列来保护这4个二维约束码字， 该特殊的二维阵列称为二维保护字，在第一种编码规则中，这个二维保护字为如图6(a) 所示，在该编解码规则表中，一维数据字用X＝[X₁ X₂]表示，二维约束码字如下所示： 基于该编解码规则表，其对应的二维约束码字编码方程如下所示：

$Y=\left(\begin{array}{cc}{Y}_{11}& Y_{12}\\ Y_{21}& Y_{22}\end{array}\right)=\left(\begin{array}{cc}0& X_2\\ X_1& 0\end{array}\right)$

其中X1～X2为一维数据字的各个比特位。Y11～Y22为二维约束码字的各比特位。基于 此编解码规则表，可将一维2比特数据转换成2×2的二维约束码字。反之，在译码的过程中， 根据该编解码规则表，一维2比特数据字的译码方程如下所示：X₁＝Y₂₁；X₂＝Y₁₂。

图6(b)给出的是第二种编码规则表，在这个编码规则中，二维保护字是基于该编解 码规则表，其对应的二维约束码字编码方程如下所示：和6(b) 对应的一维2比特数据字的译码方程如下所示：

X₁＝Y₁₁；X₂＝Y₂₂

如图7所示，在二维约束阵列的构造中，字单元行编号是二维数据输入的先后顺序，即 2×2的二维数据首先输入到字单元第一行，依次类推，直至2×2的二维数据输入到最后一行， 这里二维数据字单元页的最后一行用字单元第N行来描述。

如图8所示，编码器编码过程如下：首先原始的一维数据流输入到数据缓冲及分组模块。 该模块在缓冲一维数据流的同时，根据二维阵列的大小，将数据划分成若干个长度相等的分 组，一维数据流经过分组模块后，首先将分组数据输入到二维码字生成模块，然后再根据图 6描述的编码规则表，生成相应的二维约束码字，并输入到二维字单元模块。其中二维字单 元构造模块根据二维约束码字的大小，将2N×2M的二维阵列划分成若干个由2×2阵列组成 的N×M的二维字单元页。二维数据阵列的生成是由二维码字写入阵列模块来完成。二维码字 写入模块阵列将由二维码字生成模块产生的二维约束码字按照图7所示二维字单元页斜线方 向的奇数行从右上角到左下角顺序逐行将二维约束码字写入到二维阵列中。保护字填充模块 依据编码过程选取的编解码规则表，选取对应的保护字，沿图7所示的二维字单元页斜线方 向的偶数行顺序，将二维保护字逐行填入到的二维数据阵列，从而实现一维数据流到二维约 束阵列的转化，上述将一维数据序列的二维阵列编码过程。其编码步骤包括：

(1)对输入的任意长度数据流根据二维阵列尺寸进行分组；

(2)以2个比特为一个字将步骤(1)中的一维数据分组划分成若干个一维数据字，然 后根据图6所述的编解码规则表，将2比特的一维数据字编码成2×2的二维约束码字；

(3)以2×2为一个字单元，逐行对二维阵列进行划分以字单元为最小单位的二维字单 元页；

(4)判断步骤(3)中的二维阵列是否划分完毕，满足转步骤(5)，否则继续步骤(3)；

(5)将步骤(2)得到的二维约束码字沿着二维字单元页斜线方向的奇数行逐行写入；同 时将对应的二维保护字沿二维字单元页斜线方向的偶数行逐行填充；

(6)将步骤(5)得到的二维数据约束阵列输出到二维记录装置。

如图9所示，编码器解码过程如下：首先从二维记录装置读取二维数据阵列，然后从二 维阵列缓冲模块逐页读取数据，输入到二维字单元页构造模块，按照2×2为一个字单元，将 二维数据阵列划分成二维字单元页，然后将划分后的二维字单元页输入到二维字单元读取模 块读取二维字数据，将二维数据字输入到一维数据字译码模块，得到相应的一维数据字，将 一维数据字输入到一维数据流组装模块，按照数据字的先后次序组装成一维原始数据流，从 而完成二维约束阵列到一维数据流的转化，实现解码过程。其解码步骤包括：

(1)将二维阵列按照2×2为基本单元划分成二维字单元页；

(2)沿着字单元页斜线方向的奇数行逐行读取二维数据；

(3)根据图6的编解码规则表，将步骤(2)得到的2×2二维数据译码成2比特一维数据 字；

(4)将步骤(3)得到的一维数据字按照先后次序组装成一维数据流并输出，译码完成。

为了说明编码规则的应用方法，图10和图11列举了本发明的一个编码实施例1和解码 过程的实施例2。实施例1和实施例2均依据图6(a)所描述的编解码规则表，二维阵列的 大小等于8×8。若依据图6(b)所描述的编解码规则表，其实施类似。

实施例1：

图10给出了具体的编码过程。一维数据流首先划分成若干个长度相等的数据分组。数据 分组的长度依据二维阵列大小来确定，在本实施例中，因二维阵列大小等于8×8，因此每组的 数据包括16个比特，这16个比特数据按照两两一个字，划分成8个字，即每组数据包括8 个2比特字。然后这8个一维数据字根据图6(a)的编码规则进行编码。这个编码规则如下： 上述8个一维数据字被编码成8个2×2的二维 约束码字后，通过二维阵列写入模块，沿着二维字单元页奇数行逐行写入到二维阵列，写入 后的二维阵列如下：

当二维约束码字写入完成，即沿着二维字单元的偶数行逐行填充二维数据保护字得 到满足约束限制的8×8二维数据阵列，再将该约束阵列传输给二维记录装置，即可完成一页 用户数据的二维记录。该二维约束数据阵列如下：

实施例2：

图11给出了具体的译码过程。首先从二维记录装置读取二维数据阵列。在本实施例中， 这个8×8的二维数据阵列如下：

$\left(\begin{array}{cccccccc}0& 1& 0& 1& 0& 0& 0& 1\\ 0& 0& 1& 0& 0& 0& 1& 0\\ 0& 1& 0& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 0& 0& 0\\ 0& 1& 0& 1& 0& 0& 0& 1\\ 0& 0& 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 0& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 0& 0& 0\end{array}\right)$

然后将该二维数据阵列以2×2为一个基本单元，水平逐行划分成大小等于4×4的二维 字单元页，划分后的二维字单元页如下：

然后沿着二维字单元页斜线方向的奇数行逐行读取2×2的二维数据子阵列，在本实施例 中，读取的2×2二维数据子阵列按照图6(a)的编解码规则译码，这个过程如下：

$\left(\begin{array}{c}01\\ 00\end{array}\right)->01;$$\left(\begin{array}{c}00\\ 00\end{array}\right)->00;$$\left(\begin{array}{c}01\\ 10\end{array}\right)->11;$$\left(\begin{array}{c}01\\ 00\end{array}\right)->01;$$\left(\begin{array}{c}01\\ 00\end{array}\right)->01;$$\left(\begin{array}{c}00\\ 10\end{array}\right)->10;$$\left(\begin{array}{c}00\\ 10\end{array}\right)->10;$$\left(\begin{array}{c}01\\ 00\end{array}\right)->01.$

最后将“01 00 11 01 01 10 10 01”这些一维数据字组装成用户数据流 0100110101101001并输出，即可完成用户数据的二维解码。

基于图6(b)的编解码规则，也可完成类似地编码解码工作。尽管已经详细描述了本发 明公开的实施例，但应理解在不脱离基于图6的两种编解码规则表及相应二维数据保护字构 思和范围的情况下，本发明在具体实施例还有很多变化、替代和修改。