本发明属于数据存储领域和通信领域。具体涉 及当将二进制数据存储在矩形 格子组成的平面上，无论是在水平方向还是在 垂直两个方向上，在连续数据" 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 X 2的二维约束码字；

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

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

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

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

所述解码器包括：

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

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

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

一维数据流组装模块，该模块将一维数据字按 照产生的先后顺序组装成一维 数据流； 上述五个模块依次连接， 最后通过其中的一维数据流组装模块输出。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

图 3是满足二维 2D- (1， 3) RLL约束的二维数据阵列示意图。 图 4是 4个方形格子构成的二维字单元。

图 5是二维阵列 （6 X 6 ) 划分成二维字单元页 （3 X 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约束编 码方法， 包括下述步骤：

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

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

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

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

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

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

解码步骤如下：

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

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

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

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

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

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

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

二维码字生成模块， 该模块根据图 6描述的编解码规则表， 生成相应的二维 约束码字， 并输入到二维字单元模块； 二维字单元页构造模块， 该模块将二维数据页划分成若干个 2 X 2的二维数 据子阵列组成的二维字单元页；

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

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

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

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

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

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

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

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

下面结合附图和实施例对本发明作进一步的详 细说明： 如图 3所示， 描述本发明产生的二维数据阵列， 该阵列无论是在水平方向还 是在垂直方向上， 在相邻数据 "1"之间， 数据 "0"的游程长度都满足最小等于 1， 最多不超过 3的约束条件。

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

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

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

基于该编解码规则表， 其对应的二维约束码字编码方程如下所示：

其中 X1〜X2为一维数据字的各个比特位。 Y11〜Y22为二维约束码字的各比 特位。基于此编解码规则表， 可将一维 2比特数据转换成 2X2的二维约束码字。 反之， 在译码的过程中， 根据该编解码规则表， 一维 2比特数据字的译码方程如 下所示： ^ = _{1 ;} X ₂ =F ₁₂ 。 图 6(b)给出的是第二种编码规则表， 在这个编码规则中， 二维保护字是 ¹⁽⁾ 。

01 基于该编解码规则表， 其对应的二维约束码字编码方程如下所示： 和 6(b)对应的一维 2比特数据字的译码方程如下所 γ — V . γ — V

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

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

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

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

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

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

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

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

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

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

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

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

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

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

实施例 1:

图 10给出了具体的编码过程。 一维数据流首先划分成若干个长度相等的数 据分组。数据分组的长度依据二维阵列大小来 确定， 在本实施例中， 因二维阵列 大小等于 8X8，因此每组的数据包括 16个比特， 这 16个比特数据按照两两一个 字， 划分成 8个字， 即每组数据包括 8个 2比特字。然后这 8个一维数据字根据 图 6 (a)的编码规则进行编码。这个编码规则如下： 00- > ； 01- > ； 10- > ；

11-〉 。 上述 8个一维数据字被编码成 8个 2X2的二维约束码字后， 通过二 维阵列写入模块， 沿着二维字单元页奇数行逐行写入到二维阵列 ， 写入后的二维 阵列如下：

01 00

00 00

01 01

10 00

01 00

00 10

00 01

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

实施例 2:

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

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

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

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

01 00 01 01 01 00 00

->01； ->00； ->11； ->01； ->01； ->10； ->10； 00 00 10 00 00 10 10

01

-> 01。最后将 "01 00 11 01 01 10 10 01 "这些一维数据字 00

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