2024年6月12日发(作者：崇修雅)
(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(21)申请号 CN03807686.1
(22)申请日 2003.03.14
(71)申请人 皇家飞利浦电子股份有限公司;索尼株式会社
地址 荷兰艾恩德霍芬
(72)发明人 M·E·范迪克 K·亚马莫托 M·哈特托里
(74)专利代理机构 中国专利代理(香港)有限公司
代理人 李亚非
(51)
H03M13/29
G11B20/18
(10)申请公布号 CN 1647393 A
(43)申请公布日 2005.07.27
权利要求说明书 说明书 幅图
(54)发明名称
装置
(57)摘要
本发明涉及将纠错附加层嵌入纠错
将纠错附加层嵌入纠错码的方法和
码的方法，其中信息被编码到第一伽罗瓦
域上的代码的码字中，其中多个码字被排
列在包括用户数据子块和奇偶校验数据子
块的编码块列中。为了提供易于实现、保
持兼容性并能提高纠错能力的纠错附加
层，提出的方法包括以下步骤：利用比第
一伽罗瓦域大的第二伽罗瓦域上的水平纠
错码独立或成组地对用户数据子块的行编
码，以便获得水平奇偶校验，将水平奇偶
校验作为附加层嵌入纠错码。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.将纠错附加层嵌入纠错码的方法，其中信息编码在第一伽罗瓦域上的代码的码字
中，其中多个码字排列在包含用户数据子块和奇偶校验子块的代码块列中，该方法
包括以下步骤：
-利用比所述第一伽罗瓦域大的第二伽罗瓦域上的水平纠错码独立或成组地对至少
所述用户数据子块的行编码，以便获得水平奇偶校验，
-将所述水平奇偶校验作为附加层嵌入纠错码。
2.权利要求1的方法，其中在对所述用户数据子块编码之前，将具有预定义值的预
定义数目的比特添加到所述用户数据子块的每个符号中。
3.权利要求2的方法，其中将具有零比特值的一个或两个比特添加到所述用户数据
子块的每个符号中。
4.权利要求1的方法，其中所述代码块是包含LDC码字，特别是第一伽罗瓦域
GF(28)上的码字，的长距码LDC，并排列在LDC块的列中。
5.权利要求4的方法，其中利用伽罗瓦域GF(29)上的[306，304，3]Reed Solomon
代码独立地对用户数据子块的每行编码。
6.权利要求4的方法，其中利用Reed Solomon码的子空间子码，特别是伽罗瓦域
(29)上的Reed Solomon码的子空间子码，独立地对所述用户数据子块的每行编码。
7.权利要求4的方法，其中利用伽罗瓦域GF(210)上的ReedSolomon代码，以至少
两个连续行为一组，特别是三个连续行，成组地对用户数据子块的行编码。
8.权利要求4的方法，其中利用Reed Solomon码的子空间子码，以至少两个连续
行为一组，成组地对所述用户数据子块的行编码，特别是利用伽罗瓦域GF(210)上
的Reed Solomon码的子空间子码，以三个连续行为一组，成组地对用户数据子块
的行编码。
9.权利要求1的方法，其中独立或成组地对完整代码块的行编码。
10.权利要求1的方法，其中利用附加纠错码，特别是包含GF(28)上的
Reed Solomon代码的脉冲串指示子码BIS，对水平奇偶校验编码。
11.对根据权利要求1的方法，在其中嵌入了纠错附加层的纠错码解码的方法，其
中信息编码在第一伽罗瓦域上的代码的码字中，其中多个码字排列在包含用户数据
子块和奇偶校验子块的代码块列中，该方法包括以下步骤：
-从纠错码中提取水平奇偶校验，
-利用比使用水平奇偶校验的第一伽罗瓦域大的第二伽罗瓦域上的、已经在权利要
求1的方法中用于编码的水平纠错码独立或成组地对至少用户数据子块的行解码。
12.将纠错附加层嵌入纠错码的装置，其中信息编码在第一伽罗瓦域上的代码的码
字中，其中多个码字排列在包含用户数据子块和奇偶校验数据子块的代码块的列中，
该装置包括：
-利用比第一伽罗瓦域大的第二伽罗瓦域上的水平纠错码独立或成组地对至少所述
用户数据子块的行编码，以便获得水平奇偶校验的方法，
将水平奇偶校验作为附加层嵌入纠错码的方法。
13.对根据权利要求1的方法在其中嵌入了纠错附加层的纠错码解码的装置，其中
信息编码在第一伽罗瓦域上的代码的码字中，其中多个码字排列在包含用户数据子
块和奇偶校验子块的代码块列中，该装置包括：
-从纠错码中提取水平奇偶校验的装置，
-利用比使用水平奇偶校验的第一伽罗瓦域大的第二伽罗瓦域上的、已经在权利要
求1的方法中用于编码的水平纠错码独立或成组地对至少用户数据子块的行解码的
装置。
14.按照根据权利要求1的方法，以将纠错附加层嵌入其中的纠错码的码字的形式
存储数据的存储介质，其中水平奇偶校验作为附加层嵌入纠错码中，多个所述代码
的码字被排列在包括用户数据子块和奇偶校验数据子块的编码块列中。
15.包含以根据权利要求1的方法将纠错附加层嵌入其中的纠错码的码字的形式存
在的数据的信号，其中水平奇偶校验作为附加层嵌入纠错码，多个代码的码字被排
列在包括用户数据子块和奇偶校验数据子块的编码块列中。
16.包含在程序在计算机上运行时，能够使计算机实现权利要求1或11的方法的各
个步骤的程序代码方法的计算机程序。
说 明 书
本发明涉及将纠错附加层嵌入纠错码的方法，其中信息被编码到第一伽罗瓦域上的
代码的码字中，其中多个码字被排列在包括用户数据子块和奇偶校验数据子块的编
码块列中。本发明还涉及对这种纠错码解码的方法、以及相应的装置、存储这种编
码的码字的存储媒质、包含这种码字的信号和实现该方法的计算机程序。
利用分字交错(wordwise interleaving)对多字信息编码的方法公开在WO 00/07300中。
在那里，描述了一种包含两种类型的码字，长程码LDC(Long Distance Code)和突
发指示子码BIS(BurstIndicator Subcode)，的所谓的哨兵码(picket code)，该编码已
被确定用于DVR(数字视频记录)，以便在光记录载体上存储数据，特别是视频数
据。BIS码字提供较强的纠错能力。即使在最恶劣的情况下，不能对其正确解码几
乎不可能。在对BIS列解码之后，可以将突发错误识别出来。在应用擦除策略之
后，也能对纠错能力较弱的LDC码字正确解码。
与已有的纠错码相比，例如DVD中的乘积码(product code)，哨兵码提高了纠正(多
个)突发错误的能力。然而，哨兵码纠正随机错误的能力较弱。因此，本发明的目
的是提供一种提高纠错能力，特别是纠正随机错误，的方法，该方法易于实现且兼
容现有纠错码方案。所述的方法可以应用于任何纠错码，特别是用于DVR的哨兵
码。
该目的是通过权利要求1的方法实现的，包括以下步骤：
-利用水平纠错码在大于第一伽罗瓦域的第二伽罗瓦域上独立或成组地对用户数据
块的行编码，以便获得水平奇偶校验，
-将水平奇偶校验作为附加层嵌入纠错码。
本发明基于常规概念，即对排列在代码块列中的码字产生水平奇偶校验。因为代码
块的域大小，即代码块的每行的长度，通常大于代码块列中的码字所归属的第一伽
罗瓦域上的最长代码，所以使用更大伽罗瓦域上的代码。更大伽罗瓦域的大小应该
使得较大伽罗瓦域上的代码的码字长度大于需要产生附加水平奇偶校验的代码块的
行的长度。然后，所产生的水平奇偶校验作为附加层嵌入原始代码，用于纠错。该
附加层在解码过程中使用，用于纠正擦除、突发错误和解码故障。因为所获得的水
平奇偶校验受到额外的保护，所以根据本发明可以获得高水平的纠错能力。
本发明还涉及对根据上述编码方法将纠错附加层嵌入其中的纠错码解码的方法，该
方法包括以下步骤：
-从纠错码中提取水平奇偶校验，
-利用已经在权利要求1所述的方法中用于编码的水平纠错码，在比使用水平奇偶
校验的第一伽罗瓦域大的第二伽罗瓦域上独立或成组地对至少用户数据字块的行解
码。
此外，本发明还涉及权利要求12和13所述的相应装置，以及按照将纠错附加层嵌
入其中的纠错码的码字形式存储数据的存储媒质，特别是光记录载体例如CD、
DVD或DVR盘，包含权利要求15所述的码字形式的数据的信号，和包含当程序
在计算机上运行时能够使计算机实现权利要求1或11所述的方法的程序代码方法
的计算机程序。本发明的优选实施方案定义在附属权利要求中。
为了在较大的伽罗瓦域上对行编码，在编码前，将具有预定义值的预定义数目的比
特添加到用户数据子块的每个符号上。最容易的方法是向每个符号添加一个零比特
值的比特。然而，一般情况下，任何其它比特值都是可以的。还可能的是，将具有
任何比特值的比特添加到每个符号，即不是所有的比特都需要具有相同的比特值。
然而，有必要将添加的比特序列存储在一行的符号中，因为必须将相同的序列添加
到每一行。在这种情况下，需要存储该序列的寄存器。然而，当添加零比特值的比
特时，不需要用于存储的寄存器；此外，执行的“与”操作也较少。
优选的是，本发明应用于使用如DVR所采用的哨兵码的方法，其中代码块是包含
排列在LDC块列中的LDC码字，特别是GF(28)上的[248，216，33]码字，的
LDC块，其中还使用了BIS码字，特别是GF(28)上的[62，30，33]Reed Solomon
码字。优选的是，获得的水平奇偶校验由附加的纠错码编码，即当使用哨兵码
picketcode时，优选地对水平奇偶校验编码并写入BIS码字。
当将本发明应用于哨兵码picket code时，用户数据子块的每行都优选地利用伽罗
瓦域GF(29)上的[306，304，3]Reed Solomon(RS)代码编码。这意味着将一个额外
的比特添加到用户数据子块的每个符号上，所以每个符号包含9个比特。如上所述，
优选的是将一个零比特值的比特添加到每个符号上。利用GF(29)上的代码，可以
获得两个额外的水平奇偶校验列。
根据另一优选实施方案，Reed Solomon子空间子码(SSRS)代码将用于对用户数据
子块的行编码。该Reed Solomon子空间子码代码具体地描述在i，
ce，n“Subspace subcodes of Reed-Solomon codes”，
IEEEtransactions on IT，vol.44，no.5，September 1998。该SSRS代码是一种在所有
码字中的所有符号的特定比特总为零的代码。与通常的Reed Solomon代码相比，
需要较少的奇偶校验比特，其代价是附加的用户数据比特。将这种SSRS代码应用
于哨兵码时，使用伽罗瓦域GF(29)上的[307，305，3]SSRS代码。
如果不是独立地对每行编码，而是至少两行一组地对行编码，还可以获得额外的好
处，例如首先将三行合并成一个较长的行，然后获得其水平奇偶校验。应用于哨兵
码，优选地使用GF(210)上的[916，912，5]RS代码，需要将每个符号扩展两个比
特，优选的是零值比特。
在优选实施方案中，SSRS代码的使用应用于至少由两个连续行构成的组，这将进
一步减少所需的水平奇偶校验的数目。特别是在对哨兵码的应用中，使用了
GF(210)上的[917，913，5]SSRS代码。
下面将参考附图详细地对本发明进行解释，其中
图1示出哨兵码的编码过程的示意性过程，
图2示出根据本发明的编码装置的框图，
图3示出根据本发明的编码方法的第一实施方案，
图4示出根据本发明的解码装置的框图，
图5示出根据本发明的编码方法的第二实施方案，
图6示出根据本发明的编码方法的第三实施方案，和
图7示出根据本发明的编码方法的第四实施方案。
图1示出编码方法的示意性过程，如WO 00/07300所描述的。从可以是主机或应
用程序的源收到的用户数据首先被分割成数据帧，每帧包括2048+4字节；如图1
中的方框200所示，这些帧中的32个将在下一编码步骤中使用。在方框202，组
成数据块，并排列成216行、304列的数据块。在方框204，通过添加32个行奇偶
校验构成长程码(LDC)块。在方框206，ECC簇排列成152列496行。这样排列是
为了将标号为ECC的四个部分填充在物理簇块218中，那是全面(comprehensive)
代码格式NTT。
记录系统添加的地址和控制数据也在连续的步骤中转换。首先，逻辑地址和控制数
据在方框208中排列成32×18字节。逻辑地址是那些属于功能性使用的数据，可以
指示涉及用户程序的运行时间的方面。同样，物理地址在方框210中排列成16×9
字节。物理地址涉及记录载体上的物理距离，例如光盘。由于重复进行编号和交错，
物理和逻辑地址间的联系将被打破。在程序中紧密相随的项将相互间隔开一定的物
理距离，反之亦然。同样，映射不是均匀进行的。在方框212，地址和并到24列
30行的存取方框中。在方框214，具有32个添加了奇偶校验的行。在方框216，
这些被排列成3列496行的突发指示子码Burst Indicator Subcode(BIS)簇。这些填
充方框218中的3个BIS列。同样，添加了一列同步比特组，这样就构成了155列
496行的物理簇。这些一起构成分组成496个记录帧的16个物理部分，如图所示。
上述包含LDC码字和BIS码字的纠错码通常称为哨兵码，并应用于DVR技术。
关于该代码的进一步细节，特别是该代码的编码和解码设备，代码格式，交错和映
射的方法，帧格式，请参考在此引用作为参考的WO 00/07300。
图2示出了根据本发明用于编码，特别是将第三纠错层嵌入图1所示的、包含
LDC和BIS两层的装置的框图。图3示出了该编码方法的各个步骤对代码的影响。
利用这些图，将可以解释将纠错附加层嵌入哨兵码picket code的过程。
在第一步骤，来自信息源10，例如来自传输通道、应用程序或存储媒体，的用户
数据被编码成304 LDC码字，该码字是伽罗瓦域GF(28)上的[248，216，
33]Reed Solomon码字。该编码步骤由LDC编码器11实现，并形成包含用户数据
子块L1和奇偶校验数据子块L2的LDC块L。每个LDC码字c包含216个用户数
据符号和32个奇偶校验符号，并排列成LDC块L的列。假定产生随机错误，最有
可能的情况是在304个LDC码字中只有一个c导致解码器故障。为了纠正LDC码
字中的解码器故障，将引入ECC第三层。GF(28)上的RS代码不能直接使用，因
为GF(28)上的最长RS代码的长度是255，小于长度为304的LDC块L行的长度。
因此，根据本发明，采用GF(29)上的Read Solomon[306，304，3]代码作为第三层
ELC。
如图3a所示，矩阵V1用于更进一步的编码，其中V1对应于原始码块L的用户数
据子块L1。利用比特插入器12，一个零比特值的比特添加到矩阵V1的每个符号，
使得每个初始包含8个比特的符号现在包含9个比特，其中的最后一个比特具有为
零的比特值。随后，第三层ECC编码器13利用GF(29)上的系统的RS[306，304，
3]代码对矩阵V1的每行编码。这样，每行产生两个均包含9个比特的奇偶校验符
号。因而，总共获得了两个附加的奇偶校验符号列V2。
图3b示出所获得的单个水平码字h1。码字h1包含初始(8比特)符号h11，附加的
零值比特(h13)和获得的两个均包含9个比特的奇偶校验符号h12。
其后，所产生的水平奇偶校验符号V2由第三层ECC奇偶校验提取器14提取，并
进行编码，最后由BIS编码器15利用[62，30，33]RS代码写入BIS码字。这是可
能的，因为在哨兵码的现有格式中，BIS码字中的567个字节没有定义，其中的
486(216×(2×9)/8)个字节用于嵌入所谓的水平奇偶校验。用于编码的其它信息符号
由BIS信息源17传送到BIS编码器15。哨兵码现有格式的其余部分保持不变；第
三层只包括所获得的486个水平奇偶校验字节。
在交错器16中，BIS码字最终如WO 00/07300所述的那样，在交错后的数据流输
出到调制器18进行进一步处理之前，交错到LDC码字中。因为根据本发明提出的
第三层与众知的纠错编码和解码方案兼容，DVR播放器不需要执行第三层的解码。
下面将参考图4更加详细地解释对包含上述第三纠错层的扩展哨兵码的解码，该图
示出根据本发明的解码装置的框图。哨兵码通过解码BIS码字、应用擦除策略和
解码LDC码字进行解码。下面将进一步解释根据本发明嵌入哨兵码的第三层如何
针对LDC码字的一次或两次解码故障提供保护的。
首先，利用BIS-LDC分离器21从由解调器20接收到的、包含BIS码字和LDC码
字的数据流中提取BIS码字，并利用BIS解码器22对BIS码字解码。其中，只进
行唯错误error-only解码。因为BIS码字受到高纠错能力的保护，所以可以假定所
有BIS码字都能正确解码。因此，图3所示的矩阵V的每个217[219，217，3]RS
码字的两个奇偶校验是已知的。此外，这还提供了关于突发错误的知识，因为突发
错误将影响相邻的BIS字节，这种识别导致擦除怀疑已发生突发错误的LDC字节，
即擦除在方框23进行。现在，LDC解码器24利用错误-擦除解码策略对LDC码字
解码，即重构可能包含错误和擦除的代码块L。
然后，对于用户数据子块L1，比特插入器26插入一个零值比特，将子块L1的每
个比特扩展一个比特。因此，利用第三层ECC解码器28，所获得的矩阵V由
GF(29)上的RS[306，304，3]解码，利用第三层ECC奇偶校验提取器25提取的水
平奇偶校验和从擦除宣告单元27获得的关于在初始代码块L中的擦除位置的知识，
进行解码。根据由ECC解码器28获得的正确矩阵V，利用零值比特剥离器29将
插入的零值比特再次从每个符号中删除，从而获得包含用户数据的用户数据子块
L1，该子块最终输出到信息接收器30，例如应用程序或传输通道。
ECC第三层可以纠正一些下述的LDC码字的解码器故障和解码器错误：
a)LDC码字中的两次解码器故障和零次解码器错误：宣告与每个RS[306，304，3]
码字上的两次解码器故障相对应的两次擦除，利用唯擦除(erasure-only)解码对
GF(29)上的RS[306，304，3]码字解码。
b)LDC码字中的一次解码器故障和零次解码器错误：利用唯错误(error-only)解码对
GF(29)上的RS[306，304，3]码字解码。因为RS[306，304，3]代码可以纠正一次
错误，所以能够恢复解码器故障。
c)LDC码字中的零次解码器故障和一次解码器错误：利用唯错误error-only解码对
GF(29)上的RS[306，304，3]码字解码。因为RS[306，304，3]代码可以纠正一次
错误，所以能够恢复解码器错误。
本发明解码方法的另一实施方案示于图5a。其中，利用GF(29)上的Reed Solomon
子空间子码(SSRS)代码代替了GF(29)上的RS代码。SSRS代码是一种所有码字中
的所有符号的某些比特总为零值的代码，即SSRS代码是RS代码的线性子码
linear subcodes。关于这种SSRS代码的更多细节请参考上述的i等人的文
章。
根据图5a所使得实施方案，GF(29)上的SSRS[307，305，3]代码是根据从GF(29)
上的RS[306，304，3]代码通过将所有码字中的所有符号的最后一个比特设定为零
值而构建的，以每个信息符号一个比特的代价包含奇偶校验符号。这由图5b所示
的矩阵V的一个水平码字h2示出。码字h2包含初始用户数据字块L1的304个信
息符号h21，每个符号包含8个比特，并向每个符号添加一个比特值为零的比特
(h23)。此外，码字h2还包含三个附加的符号，每个符号包含作为最后一个比特的、
比特值为零的比特，填充最后两个8-比特符号和倒数第三个符号中的一个附加比
特的17个奇偶校验比特h22。倒数第三个符号中的其余7个比特h24保持为空。
与GF(29)上的RS[306，304，3]相比，GF(29)上的SSRS[307，305，3]需要更少的
奇偶校验比特。GF(29)上的RS[307，305，3]需要8×2+1＝17个比特(因为所有包含
h25的最后一个比特都设定为零值)，而GF(29)上的RS[306，304，3]需要9×2＝18
个比特。因为矩阵V包含216个SSRS[307，305，3]码字，所以利用GF(29)上的
SSRS[307，305，3]代替GF(29)上的RS[306，304，3]总共可以节省1×216/8＝27
个字节。然而，如果将GF(29)上的SSRS[307，305，3]用作ECC第三层，那么可
以实现相同的纠错能力，因为GF(29)上的SSRS代码是GF(29)上的RS代码的一个
特殊形式。
本发明解码方法的第三实施方案示于图6a。其中，比GF(29)更大的域用于对一个
码字中的几个连续行编码。在第一和第二实施方案中，矩阵V的一行构成一个
GF(29)上的RS[306，304，3]码字，GF(210)上的RS[916，912，5]能够将三行编码
为一个码字。
为了获得更大的域，需要将两个比特值为零的比特而不是一个添加到用户数据字块
L1的每个符号中，从而获得矩阵V1’。通过对每一行编码，可以获得四个附加的
奇偶校验符号列V2’，同时形成矩阵V’。
单个水平码字h3示于图6b。每个码字h3包含三个连续的用户数据符号行h311、
h312和h313，每行将添加两个零比特值的比特h33，还包含四个10比特的符号，
每个通过对三个包含附加的零值h33的连续行h311、h312和h313编码而获得的奇
偶校验h32。
与GF(29)上的RS[306，304，3]相比，该代码节省126个奇偶校验字节，并且具有
几乎相同的纠错能力。当使用图4所示的类似解码器时，只能纠正LDC码字中的
一个解码器故障。一个解码器故障对应于可以纠正四次擦除的GF(210)上的
RS[916，912，5]中的三次擦除。然而，如果LDC码字在第三层的唯错误errors-
only解码之后再次解码，那么在许多情况下就可以恢复两次解码器故障或一次解码
器错误，因为在假设随机错误的前提下，LDC解码之后剩余的错误符号处于一个
GF(210)上的RS[916，912，5]码字的可能性非常小。此外，当LDC和第三层之间
的反复解码次数增加时，将可以获得比单次解码更好的性能。
根据另一可供选择的实施方案，利用GF(210)上的RS[916，912，5]，可以保护代
码块L的所有248行，即用户数据子块L1的所有行和奇偶校验数据子块L2，可以
反复对第三层和LDC解码。这将导致比只保护用户数据子块L1更好的性能，其
代价是54个额外的奇偶校验字节。在该可供选择的实施方案中，LDC块L的奇偶
校验字节也受到第三层的保护，即生成并保护奇偶校验的奇偶校验。奇偶校验的奇
偶校验提供了比GF(210)上的216 RS[916，912，5]还大的完全扩展哨兵码
picket code的最小距离，因为第三层和LDC构成一类用在DVD中的乘积码
product code。一般而言，具有较大最小距离的乘积码product code可以通过迭代编
码实现较好的性能。应当注意的是，该可供选择的实施方案的基本想法，即对即偶
校验数据子块L2的行编码，可以应用于任何其它实施方案。
本发明编码方法的另一实施方案示于图7a。该实施方案将示于图5a和图6a的第二
和第三实施方案的两种想法结合在一起，即SSRS代码和对一个码字的多行编码。
根据该实施方案，矩阵V1’的三个连续行同时利用GF(210)上的RS[917，913，5]
代码编码，总共获得38个奇偶校验字节。
一个这样的码字h4示于图7b。它包括用户数据符号的三个连续行h411、h412、
h413，每行都添加两个比特值为零的比特h43，所获得的、位于最后五个符号中38
个奇偶校验比特h42和两个空比特h44。因为也使用SSRS代码，所以码字h4的最
后五个符号的最后两个比特被设定为零值。
在另一可供选择的实施方案中，如果LDC块L的所有248行都受到GF(210)上的
SSRS[917，913，5]的保护，如果第三层和LDC迭代进行编码，那么将可以获得比
GF(210)上的216 SSRS[916，912，5]更好的性能，其代价是51个额外的奇偶校验
字节。
总之，本发明提高了随机错误的纠错能力，同时保持与现有纠错码方案兼容性。本
发明使我们能够选择在冗于性和纠错能力之间的平衡点，并且易于由解码器实现。
2024年6月12日发(作者：崇修雅)
(19)中华人民共和国国家知识产权局
(12)发明专利说明书
(21)申请号 CN03807686.1
(22)申请日 2003.03.14
(71)申请人 皇家飞利浦电子股份有限公司;索尼株式会社
地址 荷兰艾恩德霍芬
(72)发明人 M·E·范迪克 K·亚马莫托 M·哈特托里
(74)专利代理机构 中国专利代理(香港)有限公司
代理人 李亚非
(51)
H03M13/29
G11B20/18
(10)申请公布号 CN 1647393 A
(43)申请公布日 2005.07.27
权利要求说明书 说明书 幅图
(54)发明名称
装置
(57)摘要
本发明涉及将纠错附加层嵌入纠错
将纠错附加层嵌入纠错码的方法和
码的方法，其中信息被编码到第一伽罗瓦
域上的代码的码字中，其中多个码字被排
列在包括用户数据子块和奇偶校验数据子
块的编码块列中。为了提供易于实现、保
持兼容性并能提高纠错能力的纠错附加
层，提出的方法包括以下步骤：利用比第
一伽罗瓦域大的第二伽罗瓦域上的水平纠
错码独立或成组地对用户数据子块的行编
码，以便获得水平奇偶校验，将水平奇偶
校验作为附加层嵌入纠错码。
法律状态
法律状态公告日
法律状态信息
法律状态
权 利 要 求 说 明 书
1.将纠错附加层嵌入纠错码的方法，其中信息编码在第一伽罗瓦域上的代码的码字
中，其中多个码字排列在包含用户数据子块和奇偶校验子块的代码块列中，该方法
包括以下步骤：
-利用比所述第一伽罗瓦域大的第二伽罗瓦域上的水平纠错码独立或成组地对至少
所述用户数据子块的行编码，以便获得水平奇偶校验，
-将所述水平奇偶校验作为附加层嵌入纠错码。
2.权利要求1的方法，其中在对所述用户数据子块编码之前，将具有预定义值的预
定义数目的比特添加到所述用户数据子块的每个符号中。
3.权利要求2的方法，其中将具有零比特值的一个或两个比特添加到所述用户数据
子块的每个符号中。
4.权利要求1的方法，其中所述代码块是包含LDC码字，特别是第一伽罗瓦域
GF(28)上的码字，的长距码LDC，并排列在LDC块的列中。
5.权利要求4的方法，其中利用伽罗瓦域GF(29)上的[306，304，3]Reed Solomon
代码独立地对用户数据子块的每行编码。
6.权利要求4的方法，其中利用Reed Solomon码的子空间子码，特别是伽罗瓦域
(29)上的Reed Solomon码的子空间子码，独立地对所述用户数据子块的每行编码。
7.权利要求4的方法，其中利用伽罗瓦域GF(210)上的ReedSolomon代码，以至少
两个连续行为一组，特别是三个连续行，成组地对用户数据子块的行编码。
8.权利要求4的方法，其中利用Reed Solomon码的子空间子码，以至少两个连续
行为一组，成组地对所述用户数据子块的行编码，特别是利用伽罗瓦域GF(210)上
的Reed Solomon码的子空间子码，以三个连续行为一组，成组地对用户数据子块
的行编码。
9.权利要求1的方法，其中独立或成组地对完整代码块的行编码。
10.权利要求1的方法，其中利用附加纠错码，特别是包含GF(28)上的
Reed Solomon代码的脉冲串指示子码BIS，对水平奇偶校验编码。
11.对根据权利要求1的方法，在其中嵌入了纠错附加层的纠错码解码的方法，其
中信息编码在第一伽罗瓦域上的代码的码字中，其中多个码字排列在包含用户数据
子块和奇偶校验子块的代码块列中，该方法包括以下步骤：
-从纠错码中提取水平奇偶校验，
-利用比使用水平奇偶校验的第一伽罗瓦域大的第二伽罗瓦域上的、已经在权利要
求1的方法中用于编码的水平纠错码独立或成组地对至少用户数据子块的行解码。
12.将纠错附加层嵌入纠错码的装置，其中信息编码在第一伽罗瓦域上的代码的码
字中，其中多个码字排列在包含用户数据子块和奇偶校验数据子块的代码块的列中，
该装置包括：
-利用比第一伽罗瓦域大的第二伽罗瓦域上的水平纠错码独立或成组地对至少所述
用户数据子块的行编码，以便获得水平奇偶校验的方法，
将水平奇偶校验作为附加层嵌入纠错码的方法。
13.对根据权利要求1的方法在其中嵌入了纠错附加层的纠错码解码的装置，其中
信息编码在第一伽罗瓦域上的代码的码字中，其中多个码字排列在包含用户数据子
块和奇偶校验子块的代码块列中，该装置包括：
-从纠错码中提取水平奇偶校验的装置，
-利用比使用水平奇偶校验的第一伽罗瓦域大的第二伽罗瓦域上的、已经在权利要
求1的方法中用于编码的水平纠错码独立或成组地对至少用户数据子块的行解码的
装置。
14.按照根据权利要求1的方法，以将纠错附加层嵌入其中的纠错码的码字的形式
存储数据的存储介质，其中水平奇偶校验作为附加层嵌入纠错码中，多个所述代码
的码字被排列在包括用户数据子块和奇偶校验数据子块的编码块列中。
15.包含以根据权利要求1的方法将纠错附加层嵌入其中的纠错码的码字的形式存
在的数据的信号，其中水平奇偶校验作为附加层嵌入纠错码，多个代码的码字被排
列在包括用户数据子块和奇偶校验数据子块的编码块列中。
16.包含在程序在计算机上运行时，能够使计算机实现权利要求1或11的方法的各
个步骤的程序代码方法的计算机程序。
说 明 书
本发明涉及将纠错附加层嵌入纠错码的方法，其中信息被编码到第一伽罗瓦域上的
代码的码字中，其中多个码字被排列在包括用户数据子块和奇偶校验数据子块的编
码块列中。本发明还涉及对这种纠错码解码的方法、以及相应的装置、存储这种编
码的码字的存储媒质、包含这种码字的信号和实现该方法的计算机程序。
利用分字交错(wordwise interleaving)对多字信息编码的方法公开在WO 00/07300中。
在那里，描述了一种包含两种类型的码字，长程码LDC(Long Distance Code)和突
发指示子码BIS(BurstIndicator Subcode)，的所谓的哨兵码(picket code)，该编码已
被确定用于DVR(数字视频记录)，以便在光记录载体上存储数据，特别是视频数
据。BIS码字提供较强的纠错能力。即使在最恶劣的情况下，不能对其正确解码几
乎不可能。在对BIS列解码之后，可以将突发错误识别出来。在应用擦除策略之
后，也能对纠错能力较弱的LDC码字正确解码。
与已有的纠错码相比，例如DVD中的乘积码(product code)，哨兵码提高了纠正(多
个)突发错误的能力。然而，哨兵码纠正随机错误的能力较弱。因此，本发明的目
的是提供一种提高纠错能力，特别是纠正随机错误，的方法，该方法易于实现且兼
容现有纠错码方案。所述的方法可以应用于任何纠错码，特别是用于DVR的哨兵
码。
该目的是通过权利要求1的方法实现的，包括以下步骤：
-利用水平纠错码在大于第一伽罗瓦域的第二伽罗瓦域上独立或成组地对用户数据
块的行编码，以便获得水平奇偶校验，
-将水平奇偶校验作为附加层嵌入纠错码。
本发明基于常规概念，即对排列在代码块列中的码字产生水平奇偶校验。因为代码
块的域大小，即代码块的每行的长度，通常大于代码块列中的码字所归属的第一伽
罗瓦域上的最长代码，所以使用更大伽罗瓦域上的代码。更大伽罗瓦域的大小应该
使得较大伽罗瓦域上的代码的码字长度大于需要产生附加水平奇偶校验的代码块的
行的长度。然后，所产生的水平奇偶校验作为附加层嵌入原始代码，用于纠错。该
附加层在解码过程中使用，用于纠正擦除、突发错误和解码故障。因为所获得的水
平奇偶校验受到额外的保护，所以根据本发明可以获得高水平的纠错能力。
本发明还涉及对根据上述编码方法将纠错附加层嵌入其中的纠错码解码的方法，该
方法包括以下步骤：
-从纠错码中提取水平奇偶校验，
-利用已经在权利要求1所述的方法中用于编码的水平纠错码，在比使用水平奇偶
校验的第一伽罗瓦域大的第二伽罗瓦域上独立或成组地对至少用户数据字块的行解
码。
此外，本发明还涉及权利要求12和13所述的相应装置，以及按照将纠错附加层嵌
入其中的纠错码的码字形式存储数据的存储媒质，特别是光记录载体例如CD、
DVD或DVR盘，包含权利要求15所述的码字形式的数据的信号，和包含当程序
在计算机上运行时能够使计算机实现权利要求1或11所述的方法的程序代码方法
的计算机程序。本发明的优选实施方案定义在附属权利要求中。
为了在较大的伽罗瓦域上对行编码，在编码前，将具有预定义值的预定义数目的比
特添加到用户数据子块的每个符号上。最容易的方法是向每个符号添加一个零比特
值的比特。然而，一般情况下，任何其它比特值都是可以的。还可能的是，将具有
任何比特值的比特添加到每个符号，即不是所有的比特都需要具有相同的比特值。
然而，有必要将添加的比特序列存储在一行的符号中，因为必须将相同的序列添加
到每一行。在这种情况下，需要存储该序列的寄存器。然而，当添加零比特值的比
特时，不需要用于存储的寄存器；此外，执行的“与”操作也较少。
优选的是，本发明应用于使用如DVR所采用的哨兵码的方法，其中代码块是包含
排列在LDC块列中的LDC码字，特别是GF(28)上的[248，216，33]码字，的
LDC块，其中还使用了BIS码字，特别是GF(28)上的[62，30，33]Reed Solomon
码字。优选的是，获得的水平奇偶校验由附加的纠错码编码，即当使用哨兵码
picketcode时，优选地对水平奇偶校验编码并写入BIS码字。
当将本发明应用于哨兵码picket code时，用户数据子块的每行都优选地利用伽罗
瓦域GF(29)上的[306，304，3]Reed Solomon(RS)代码编码。这意味着将一个额外
的比特添加到用户数据子块的每个符号上，所以每个符号包含9个比特。如上所述，
优选的是将一个零比特值的比特添加到每个符号上。利用GF(29)上的代码，可以
获得两个额外的水平奇偶校验列。
根据另一优选实施方案，Reed Solomon子空间子码(SSRS)代码将用于对用户数据
子块的行编码。该Reed Solomon子空间子码代码具体地描述在i，
ce，n“Subspace subcodes of Reed-Solomon codes”，
IEEEtransactions on IT，vol.44，no.5，September 1998。该SSRS代码是一种在所有
码字中的所有符号的特定比特总为零的代码。与通常的Reed Solomon代码相比，
需要较少的奇偶校验比特，其代价是附加的用户数据比特。将这种SSRS代码应用
于哨兵码时，使用伽罗瓦域GF(29)上的[307，305，3]SSRS代码。
如果不是独立地对每行编码，而是至少两行一组地对行编码，还可以获得额外的好
处，例如首先将三行合并成一个较长的行，然后获得其水平奇偶校验。应用于哨兵
码，优选地使用GF(210)上的[916，912，5]RS代码，需要将每个符号扩展两个比
特，优选的是零值比特。
在优选实施方案中，SSRS代码的使用应用于至少由两个连续行构成的组，这将进
一步减少所需的水平奇偶校验的数目。特别是在对哨兵码的应用中，使用了
GF(210)上的[917，913，5]SSRS代码。
下面将参考附图详细地对本发明进行解释，其中
图1示出哨兵码的编码过程的示意性过程，
图2示出根据本发明的编码装置的框图，
图3示出根据本发明的编码方法的第一实施方案，
图4示出根据本发明的解码装置的框图，
图5示出根据本发明的编码方法的第二实施方案，
图6示出根据本发明的编码方法的第三实施方案，和
图7示出根据本发明的编码方法的第四实施方案。
图1示出编码方法的示意性过程，如WO 00/07300所描述的。从可以是主机或应
用程序的源收到的用户数据首先被分割成数据帧，每帧包括2048+4字节；如图1
中的方框200所示，这些帧中的32个将在下一编码步骤中使用。在方框202，组
成数据块，并排列成216行、304列的数据块。在方框204，通过添加32个行奇偶
校验构成长程码(LDC)块。在方框206，ECC簇排列成152列496行。这样排列是
为了将标号为ECC的四个部分填充在物理簇块218中，那是全面(comprehensive)
代码格式NTT。
记录系统添加的地址和控制数据也在连续的步骤中转换。首先，逻辑地址和控制数
据在方框208中排列成32×18字节。逻辑地址是那些属于功能性使用的数据，可以
指示涉及用户程序的运行时间的方面。同样，物理地址在方框210中排列成16×9
字节。物理地址涉及记录载体上的物理距离，例如光盘。由于重复进行编号和交错，
物理和逻辑地址间的联系将被打破。在程序中紧密相随的项将相互间隔开一定的物
理距离，反之亦然。同样，映射不是均匀进行的。在方框212，地址和并到24列
30行的存取方框中。在方框214，具有32个添加了奇偶校验的行。在方框216，
这些被排列成3列496行的突发指示子码Burst Indicator Subcode(BIS)簇。这些填
充方框218中的3个BIS列。同样，添加了一列同步比特组，这样就构成了155列
496行的物理簇。这些一起构成分组成496个记录帧的16个物理部分，如图所示。
上述包含LDC码字和BIS码字的纠错码通常称为哨兵码，并应用于DVR技术。
关于该代码的进一步细节，特别是该代码的编码和解码设备，代码格式，交错和映
射的方法，帧格式，请参考在此引用作为参考的WO 00/07300。
图2示出了根据本发明用于编码，特别是将第三纠错层嵌入图1所示的、包含
LDC和BIS两层的装置的框图。图3示出了该编码方法的各个步骤对代码的影响。
利用这些图，将可以解释将纠错附加层嵌入哨兵码picket code的过程。
在第一步骤，来自信息源10，例如来自传输通道、应用程序或存储媒体，的用户
数据被编码成304 LDC码字，该码字是伽罗瓦域GF(28)上的[248，216，
33]Reed Solomon码字。该编码步骤由LDC编码器11实现，并形成包含用户数据
子块L1和奇偶校验数据子块L2的LDC块L。每个LDC码字c包含216个用户数
据符号和32个奇偶校验符号，并排列成LDC块L的列。假定产生随机错误，最有
可能的情况是在304个LDC码字中只有一个c导致解码器故障。为了纠正LDC码
字中的解码器故障，将引入ECC第三层。GF(28)上的RS代码不能直接使用，因
为GF(28)上的最长RS代码的长度是255，小于长度为304的LDC块L行的长度。
因此，根据本发明，采用GF(29)上的Read Solomon[306，304，3]代码作为第三层
ELC。
如图3a所示，矩阵V1用于更进一步的编码，其中V1对应于原始码块L的用户数
据子块L1。利用比特插入器12，一个零比特值的比特添加到矩阵V1的每个符号，
使得每个初始包含8个比特的符号现在包含9个比特，其中的最后一个比特具有为
零的比特值。随后，第三层ECC编码器13利用GF(29)上的系统的RS[306，304，
3]代码对矩阵V1的每行编码。这样，每行产生两个均包含9个比特的奇偶校验符
号。因而，总共获得了两个附加的奇偶校验符号列V2。
图3b示出所获得的单个水平码字h1。码字h1包含初始(8比特)符号h11，附加的
零值比特(h13)和获得的两个均包含9个比特的奇偶校验符号h12。
其后，所产生的水平奇偶校验符号V2由第三层ECC奇偶校验提取器14提取，并
进行编码，最后由BIS编码器15利用[62，30，33]RS代码写入BIS码字。这是可
能的，因为在哨兵码的现有格式中，BIS码字中的567个字节没有定义，其中的
486(216×(2×9)/8)个字节用于嵌入所谓的水平奇偶校验。用于编码的其它信息符号
由BIS信息源17传送到BIS编码器15。哨兵码现有格式的其余部分保持不变；第
三层只包括所获得的486个水平奇偶校验字节。
在交错器16中，BIS码字最终如WO 00/07300所述的那样，在交错后的数据流输
出到调制器18进行进一步处理之前，交错到LDC码字中。因为根据本发明提出的
第三层与众知的纠错编码和解码方案兼容，DVR播放器不需要执行第三层的解码。
下面将参考图4更加详细地解释对包含上述第三纠错层的扩展哨兵码的解码，该图
示出根据本发明的解码装置的框图。哨兵码通过解码BIS码字、应用擦除策略和
解码LDC码字进行解码。下面将进一步解释根据本发明嵌入哨兵码的第三层如何
针对LDC码字的一次或两次解码故障提供保护的。
首先，利用BIS-LDC分离器21从由解调器20接收到的、包含BIS码字和LDC码
字的数据流中提取BIS码字，并利用BIS解码器22对BIS码字解码。其中，只进
行唯错误error-only解码。因为BIS码字受到高纠错能力的保护，所以可以假定所
有BIS码字都能正确解码。因此，图3所示的矩阵V的每个217[219，217，3]RS
码字的两个奇偶校验是已知的。此外，这还提供了关于突发错误的知识，因为突发
错误将影响相邻的BIS字节，这种识别导致擦除怀疑已发生突发错误的LDC字节，
即擦除在方框23进行。现在，LDC解码器24利用错误-擦除解码策略对LDC码字
解码，即重构可能包含错误和擦除的代码块L。
然后，对于用户数据子块L1，比特插入器26插入一个零值比特，将子块L1的每
个比特扩展一个比特。因此，利用第三层ECC解码器28，所获得的矩阵V由
GF(29)上的RS[306，304，3]解码，利用第三层ECC奇偶校验提取器25提取的水
平奇偶校验和从擦除宣告单元27获得的关于在初始代码块L中的擦除位置的知识，
进行解码。根据由ECC解码器28获得的正确矩阵V，利用零值比特剥离器29将
插入的零值比特再次从每个符号中删除，从而获得包含用户数据的用户数据子块
L1，该子块最终输出到信息接收器30，例如应用程序或传输通道。
ECC第三层可以纠正一些下述的LDC码字的解码器故障和解码器错误：
a)LDC码字中的两次解码器故障和零次解码器错误：宣告与每个RS[306，304，3]
码字上的两次解码器故障相对应的两次擦除，利用唯擦除(erasure-only)解码对
GF(29)上的RS[306，304，3]码字解码。
b)LDC码字中的一次解码器故障和零次解码器错误：利用唯错误(error-only)解码对
GF(29)上的RS[306，304，3]码字解码。因为RS[306，304，3]代码可以纠正一次
错误，所以能够恢复解码器故障。
c)LDC码字中的零次解码器故障和一次解码器错误：利用唯错误error-only解码对
GF(29)上的RS[306，304，3]码字解码。因为RS[306，304，3]代码可以纠正一次
错误，所以能够恢复解码器错误。
本发明解码方法的另一实施方案示于图5a。其中，利用GF(29)上的Reed Solomon
子空间子码(SSRS)代码代替了GF(29)上的RS代码。SSRS代码是一种所有码字中
的所有符号的某些比特总为零值的代码，即SSRS代码是RS代码的线性子码
linear subcodes。关于这种SSRS代码的更多细节请参考上述的i等人的文
章。
根据图5a所使得实施方案，GF(29)上的SSRS[307，305，3]代码是根据从GF(29)
上的RS[306，304，3]代码通过将所有码字中的所有符号的最后一个比特设定为零
值而构建的，以每个信息符号一个比特的代价包含奇偶校验符号。这由图5b所示
的矩阵V的一个水平码字h2示出。码字h2包含初始用户数据字块L1的304个信
息符号h21，每个符号包含8个比特，并向每个符号添加一个比特值为零的比特
(h23)。此外，码字h2还包含三个附加的符号，每个符号包含作为最后一个比特的、
比特值为零的比特，填充最后两个8-比特符号和倒数第三个符号中的一个附加比
特的17个奇偶校验比特h22。倒数第三个符号中的其余7个比特h24保持为空。
与GF(29)上的RS[306，304，3]相比，GF(29)上的SSRS[307，305，3]需要更少的
奇偶校验比特。GF(29)上的RS[307，305，3]需要8×2+1＝17个比特(因为所有包含
h25的最后一个比特都设定为零值)，而GF(29)上的RS[306，304，3]需要9×2＝18
个比特。因为矩阵V包含216个SSRS[307，305，3]码字，所以利用GF(29)上的
SSRS[307，305，3]代替GF(29)上的RS[306，304，3]总共可以节省1×216/8＝27
个字节。然而，如果将GF(29)上的SSRS[307，305，3]用作ECC第三层，那么可
以实现相同的纠错能力，因为GF(29)上的SSRS代码是GF(29)上的RS代码的一个
特殊形式。
本发明解码方法的第三实施方案示于图6a。其中，比GF(29)更大的域用于对一个
码字中的几个连续行编码。在第一和第二实施方案中，矩阵V的一行构成一个
GF(29)上的RS[306，304，3]码字，GF(210)上的RS[916，912，5]能够将三行编码
为一个码字。
为了获得更大的域，需要将两个比特值为零的比特而不是一个添加到用户数据字块
L1的每个符号中，从而获得矩阵V1’。通过对每一行编码，可以获得四个附加的
奇偶校验符号列V2’，同时形成矩阵V’。
单个水平码字h3示于图6b。每个码字h3包含三个连续的用户数据符号行h311、
h312和h313，每行将添加两个零比特值的比特h33，还包含四个10比特的符号，
每个通过对三个包含附加的零值h33的连续行h311、h312和h313编码而获得的奇
偶校验h32。
与GF(29)上的RS[306，304，3]相比，该代码节省126个奇偶校验字节，并且具有
几乎相同的纠错能力。当使用图4所示的类似解码器时，只能纠正LDC码字中的
一个解码器故障。一个解码器故障对应于可以纠正四次擦除的GF(210)上的
RS[916，912，5]中的三次擦除。然而，如果LDC码字在第三层的唯错误errors-
only解码之后再次解码，那么在许多情况下就可以恢复两次解码器故障或一次解码
器错误，因为在假设随机错误的前提下，LDC解码之后剩余的错误符号处于一个
GF(210)上的RS[916，912，5]码字的可能性非常小。此外，当LDC和第三层之间
的反复解码次数增加时，将可以获得比单次解码更好的性能。
根据另一可供选择的实施方案，利用GF(210)上的RS[916，912，5]，可以保护代
码块L的所有248行，即用户数据子块L1的所有行和奇偶校验数据子块L2，可以
反复对第三层和LDC解码。这将导致比只保护用户数据子块L1更好的性能，其
代价是54个额外的奇偶校验字节。在该可供选择的实施方案中，LDC块L的奇偶
校验字节也受到第三层的保护，即生成并保护奇偶校验的奇偶校验。奇偶校验的奇
偶校验提供了比GF(210)上的216 RS[916，912，5]还大的完全扩展哨兵码
picket code的最小距离，因为第三层和LDC构成一类用在DVD中的乘积码
product code。一般而言，具有较大最小距离的乘积码product code可以通过迭代编
码实现较好的性能。应当注意的是，该可供选择的实施方案的基本想法，即对即偶
校验数据子块L2的行编码，可以应用于任何其它实施方案。
本发明编码方法的另一实施方案示于图7a。该实施方案将示于图5a和图6a的第二
和第三实施方案的两种想法结合在一起，即SSRS代码和对一个码字的多行编码。
根据该实施方案，矩阵V1’的三个连续行同时利用GF(210)上的RS[917，913，5]
代码编码，总共获得38个奇偶校验字节。
一个这样的码字h4示于图7b。它包括用户数据符号的三个连续行h411、h412、
h413，每行都添加两个比特值为零的比特h43，所获得的、位于最后五个符号中38
个奇偶校验比特h42和两个空比特h44。因为也使用SSRS代码，所以码字h4的最
后五个符号的最后两个比特被设定为零值。
在另一可供选择的实施方案中，如果LDC块L的所有248行都受到GF(210)上的
SSRS[917，913，5]的保护，如果第三层和LDC迭代进行编码，那么将可以获得比
GF(210)上的216 SSRS[916，912，5]更好的性能，其代价是51个额外的奇偶校验
字节。
总之，本发明提高了随机错误的纠错能力，同时保持与现有纠错码方案兼容性。本
发明使我们能够选择在冗于性和纠错能力之间的平衡点，并且易于由解码器实现。