纠错编码方法及纠错编码装置

技术领域

本发明涉及依据Low-Density Parity-Check(低密度奇偶校验)码(以下称作LDPC 码)进行编码的纠错编码方法及纠错编码装置。

背景技术

纠错编码是在通信系统中纠正因通信路径中的噪声而产生的错误比特的技术。在 采用本技术的通信系统中，不是从发送设备直接发送信息数据，而是对要发送的信息 比特序列d(式1)进行被称作编码的处理，计算奇偶比特序列p(式2)，发送将信 息比特序列d和奇偶比特序列p合起来的序列即码字c(式3)。

d＝(d₁，d₂，...，d_k)   (1)

p＝(p₁，p₂，...，p_m)    (2)

c＝(d₁，d₂，...，d_k，p₁，p₂，...，p_m)    (3)

虽然发送比特速率下降奇偶比特序列p的量，但是通过在接收设备中使用信息比 特序列d和奇偶比特序列p双方进行被称作解码的处理，能够纠正或检测位于接收数 据内的错误。

LDPC码如图13所示是利用非零元素较少的稀疏的奇偶校验矩阵定义的纠错码。 在此，设矩阵元素只有0和1。奇偶校验矩阵的列数对应于码字c的比特数(码长度) n，此外，在多数情况下行数成为奇偶比特数m。信息比特序列d的比特数k为k＝n-m。

作为对LDPC码进行编码的现有技术，在非专利文献1中公开有使用下三角矩阵 的方法。在这种使用下三角矩阵的方法中，首先对奇偶校验矩阵实施后述的基本矩阵 操作，将矩阵右侧的m行m列(以下记作m×m)部分矩阵中的右上方设为0，得到 图14所示的下三角矩阵。然后，使用该下三角矩阵，通过后退代入计算奇偶比特来 进行编码。

在此，基本矩阵操作是(1)交换2个行，(2)交换2个列，(3)按照mod2将 行j与行i(i≠j)相加(即，计算异或)。

在使用下三角矩阵的现行方法中，通过对奇偶校验矩阵进行基本矩阵操作，导致 矩阵的非零元素增加，其结果是，即使奇偶校验矩阵比较稀疏，下三角矩阵也不会成 为稀疏矩阵。因此，在使用下三角矩阵的现行方法中，随着非零元素的增加，导致运 算量增大。

另一方面，在非专利文献1中还公开有与使用下三角矩阵的方法不同的以往公知 的编码方法。在该编码方法中，对上述的下三角矩阵继续实施基本矩阵操作，如图 15所示，使矩阵的右侧成为单位矩阵。在设该矩阵的左侧m×k部分矩阵为Q2时， 能够通过对信息比特序列d从左侧乘以矩阵Q2，求出奇偶比特序列p。将此时的矩 阵Q2(或者矩阵Q2的转置矩阵)称作生成矩阵。

但是，图15的生成矩阵Q2中包含的1的数量往往与图14的矩阵Q1相同或者 比矩阵Q1多。因此，与上述的使用下三角矩阵的现行方法同样，存在异或的次数多、 运算量大的问题。

现有技术文献

非专利文献

非专利文献1：和田山正著、「低密度パリティ検査符号とその復号法」トリケ ップス、2002年6月5日発行

发明内容

发明要解决的问题

过去的LDPC码的编码方法使用非零元素较多的矩阵进行编码，因而存在运算量 大的问题。另外，由于运算量大，存在电路安装时的电路规模增大的问题。

本发明正是为了解决上述问题而提出的，其目的在于，削减对LDPC码进行编码 的运算量，以及削减安装时的电路规模。

用于解决问题的手段

本发明的纠错编码方法包含：稀疏矩阵运算步骤，根据奇偶校验矩阵中与信息比 特序列对应的部分矩阵的1的位置，运算该部分矩阵与信息比特序列的异或来计算向 量；以及矩阵相乘步骤，将在稀疏矩阵运算步骤中得到的向量，与对奇偶校验矩阵中 与奇偶比特序列对应的部分矩阵实施了预先设定的基本矩阵操作后的预先设定的矩 阵相乘。

本发明的纠错编码方法包含：稀疏矩阵运算步骤，根据奇偶校验矩阵中与信息比 特序列对应的部分矩阵的1的位置，运算该部分矩阵与信息比特序列的异或来计算向 量；向量元素相加步骤，将在稀疏矩阵运算步骤中得到的向量的元素的一部分相加； 第一矩阵相乘步骤，将在向量元素相加步骤中得到的向量，与将奇偶校验矩阵中与奇 偶比特序列对应的部分矩阵的一部分相加而得到的矩阵的逆矩阵相乘，计算奇偶比特 序列的一部分；第二矩阵相乘步骤，将在第一矩阵相乘步骤中得到的奇偶比特序列的 一部分，与奇偶校验矩阵中与奇偶比特序列对应的部分矩阵的剩余部分相乘；以及奇 偶比特计算步骤，将在向量元素相加步骤中得到的向量和在第二矩阵相乘步骤中得到 的向量相加，计算奇偶比特序列的剩余部分。

在本发明的纠错编码方法中，信息比特序列d_b，i是由在将各元素按照每q个分成 块时，与第i(1≤i≤K)个块对应的q个元素构成的向量，奇偶比特序列p_b，i是由在 将各元素按照每q个分成块时，与第i(1≤i≤M)个块对应的q个元素构成的向量， M行N列的奇偶校验矩阵由与信息比特序列对应的M行K列(K＝N-M)的部分矩 阵X_ij、与奇偶比特序列对应的M行M列中第1列的部分矩阵Z_j以及2行对角成分 包含单位矩阵的部分矩阵构成，按照后述的式(24)、式(26)和式(27)计算奇偶 比特序列的各元素。

本发明的纠错编码装置具有：稀疏矩阵运算部，其根据奇偶校验矩阵中与信息比 特序列对应的部分矩阵的1的位置，运算该部分矩阵与信息比特序列的异或来计算向 量；以及矩阵相乘部，其将由稀疏矩阵运算部得到的向量，与对奇偶校验矩阵中与奇 偶比特序列对应的部分矩阵实施了预先设定的基本矩阵操作后的预先设定的矩阵相 乘。

本发明的纠错编码装置具有：稀疏矩阵运算部，其根据奇偶校验矩阵中与信息比 特序列对应的部分矩阵的1的位置，运算该部分矩阵与信息比特序列的异或来计算向 量；向量元素相加部，其将由稀疏矩阵运算部得到的向量的元素的一部分相加；第一 矩阵相乘部，其将由向量元素相加部得到的向量，与将奇偶校验矩阵中与奇偶比特序 列对应的部分矩阵的一部分相加而得到的矩阵的逆矩阵相乘，计算奇偶比特序列的一 部分；第二矩阵相乘部，其将由第一矩阵相乘部得到的奇偶比特序列的一部分，与奇 偶校验矩阵中与奇偶比特序列对应的部分矩阵的剩余部分相乘；以及奇偶比特计算 部，其将由向量元素相加部得到的向量和由第二矩阵相乘部得到的向量相加，计算奇 偶比特序列的剩余部分。

发明效果

根据本发明，将奇偶校验矩阵与信息比特序列的相乘运算分成2个步骤进行，因 而与现行方法相比，能够减小在矩阵相乘步骤中与向量相乘的非稀疏矩阵的尺寸。因 此，能够削减对LDPC码进行编码的运算量。

根据本发明，将奇偶校验矩阵与信息比特序列的相乘运算分成多个步骤进行，因 而与现行方法相比，能够减小在矩阵相乘步骤中与向量相乘的非稀疏矩阵的尺寸，并 且许多运算能够使用稀疏矩阵进行。因此，能够削减对QC(Quasi-Cyclic)-LDPC码 进行编码的运算量。

根据本发明，由于使用后述的式(24)、式(26)和式(27)，因而许多运算能够 使用稀疏矩阵进行，能够削减对QC-LDPC码进行编码的运算量。

根据本发明，将奇偶校验矩阵与信息比特序列的相乘运算分成2个步骤进行，因 而与现行方法相比，能够减小在矩阵相乘步骤中与向量相乘的非稀疏矩阵的尺寸。因 此，能够削减LDPC码的纠错编码装置的电路规模。

根据本发明，将奇偶校验矩阵与信息比特序列的相乘运算分成多个步骤进行，因 而与现行方法相比，能够减小在矩阵相乘步骤中与向量相乘的非稀疏矩阵的尺寸，并 且许多运算能够使用稀疏矩阵进行。因此，能够削减QC-LDPC码的纠错编码装置的 电路规模。

附图说明

图1是表示本发明的实施方式1的纠错编码装置的结构的框图。

图2是说明在实施方式1的纠错编码装置中使用的奇偶校验矩阵的结构的图。

图3是表示实施方式1的纠错编码装置的动作的流程图。

图4是表示本发明的实施方式2的纠错编码装置的结构的框图。

图5是表示实施方式2的纠错编码装置的动作的流程图。

图6是表示在本发明的实施方式3中使用的QC-LDPC码的一例的图。

图7是表示实施方式3的纠错编码装置的结构的框图。

图8是表示实施方式3的纠错编码装置的动作的流程图。

图9是表示本发明的实施方式4的纠错编码装置的结构的框图。

图10是说明针对图6所示的奇偶校验矩阵的基本矩阵操作的图。

图11是表示在实施方式4中使用的QC-LDPC码的一例的图。

图12是表示在实施方式4中使用的QC-LDPC码的另一例的图。

图13是说明LDPC码的奇偶校验矩阵的结构的图。

图14是说明在过去的编码方法中使用的奇偶校验矩阵的结构例的图。

图15是说明在过去的编码方法中使用的奇偶校验矩阵的另一个结构例的图。

具体实施方式

下面，为了更详细地说明本发明，参照附图来说明用于实施本发明的方式。

实施方式1

图1所示的纠错编码装置1具有稀疏矩阵运算部2、基本矩阵操作部3和矩阵相 乘部4，在LDPC码的编码中，以信息比特序列d为输入，计算满足基于奇偶校验矩 阵H的条件的奇偶比特序列p。

LDPC码的奇偶校验矩阵H和码字c具有式(4)所示的关系。

HC^T＝(0，...，0)^T   (4)

其中，设在矩阵H与向量c的相乘运算中进行的元素(比特)彼此的相加是mod2 的相加(与异或相同)。另外，T表示转置。

奇偶校验矩阵H如式(5)和图2所示。该奇偶校验矩阵H包含对应于信息比特 序列d的m×k矩阵X和对应于奇偶比特序列p的m×m矩阵Y，m×m矩阵Y为正 则矩阵。于是，能够按照式(6)所示将式(4)的左边变形。根据该式(6)和式(4) 如式(7)所示求出奇偶比特序列p。

H＝[X Y]  (5)

Hc^T＝[X Y](d₁，d₂，...，d_k，p₁，p₂，...，p_m)^T

                      (6)

＝Xd^T+Yp^T

Xd^T+Yp^T＝0

Yp^T＝-Xd^T    (7)

p^T＝Y^-1Xd^T

在上述基础上说明本实施方式1。图3是表示本实施方式1的纠错编码装置1的 动作的流程图。

在步骤ST11中，稀疏矩阵运算部2按照上式(6)运算信息比特序列d与奇偶 校验矩阵H的m×k矩阵X的异或，得到Xd^T的向量。其中，m×k矩阵X是奇偶校 验矩阵H的部分矩阵，因而比较稀疏，1的个数少。因此，本步骤ST11中的异或的 次数相比m×k次非常少。

在后面的步骤ST12中，矩阵相乘部4按照上式(4)将另行计算出的m×m矩 阵Y的逆矩阵Y^-1与步骤ST11的计算结果Xd^T相乘，得到Y^-1Xd^T的向量。逆矩阵 Y^-1是由基本矩阵操作部3根据奇偶校验矩阵H的m×m矩阵Y预先计算出的。该逆 矩阵Y^-1是m×m矩阵，不一定是稀疏矩阵。因此，在本步骤ST12中需要计算大约 m×m/2次的异或。

在本实施方式1中，异或的次数是步骤ST12的次数占主导，约为m×m/2次。 另一方面，在前面说明的现行方法中，异或的次数是m×k/2次，因而在m<k时，本 实施方式1的运算量较小。另外，在实际的纠错编码装置中使用的LDPC码几乎都满 足m<k。

如上所述，根据实施方式1，纠错编码装置1实施以下步骤：稀疏矩阵运算步骤， 根据奇偶校验矩阵中与信息比特序列对应的部分矩阵的1的位置，运算该部分矩阵与 信息比特序列的异或来计算向量；以及矩阵相乘步骤，将在稀疏矩阵运算步骤中得到 的向量，与对奇偶校验矩阵中与奇偶比特序列对应的部分矩阵实施了预先设定的基本 矩阵操作后的预先设定的矩阵(即，奇偶校验矩阵中与奇偶比特序列对应的部分矩阵 的逆矩阵Y^-1)相乘。因此，通过将奇偶校验矩阵与信息比特序列的相乘运算分成2 次进行，与现行方法相比，能够减小在相乘运算中使用的非稀疏的逆矩阵的尺寸。因 此，能够削减对LDPC码进行编码的运算量。

另外，实施方式1的步骤ST11、ST12各自的运算是比特彼此的相加和相乘，作 为一例，能够构成在异或(EXOR)门进行相加、在与(AND)门进行相乘的电路。 即，在纠错编码装置1中，稀疏矩阵运算部2和矩阵相乘部4分别由如下电路构成， 该电路由异或门和与门构成。

在该电路结构的情况下，通过与现行方法相比减小在相乘运算中使用的非稀疏的 逆矩阵Y^-1的尺寸，能够削减异或的次数，其结果是，还能够削减纠错编码装置1的 电路规模。

另外，在实施方式1中说明的纠错编码方法如式(3)所示，将码字c的向量的 左侧设为信息比特序列d，将右侧设为奇偶比特序列p，但不限于此。例如，也可以 将码字c中的任意部分设为奇偶比特序列p，在这种情况下，为了实现本实施方式1 的结构，作为一例有这样的方法，进行将码字c的元素重排的处理，使奇偶比特序列 p成为向量右侧，与此相应地也对奇偶校验矩阵H的列进行重排的处理。即使重排奇 偶校验矩阵H的列，LDPC码的本质性质也不会改变，因而能够实现这样的方法。

另外，在实施方式1中，纠错编码装置1具有基本矩阵操作部3，并且构成为对 LDPC码的奇偶校验矩阵实施基本矩阵操作，但是，该基本矩阵操作不依赖于信息比 特序列，而是仅根据奇偶校验矩阵进行运算，因而能够构成为预先求出对奇偶校验矩 阵进行基本矩阵操作而得到的运算结果，将运算结果作为数据保存到存储器等存储部 中，矩阵相乘部4使用该数据，或者构成为将运算结果组入矩阵相乘部4。在这种情 况下，能够省略基本矩阵操作部3。

实施方式2

图4是表示本实施方式2的纠错编码装置1的结构的框图。本实施方式2的纠错 编码装置1具有稀疏矩阵运算部2、基本矩阵操作部3、矩阵相乘部4和奇偶比特计 算部5。另外，在图4中对于与图1相同或者相同的部分，标注相同的标号并省略说 明。

在上述实施方式1中，说明了将上式(4)变形成上式(7)时的纠错编码方法， 在本实施方式2中说明将上式(4)变形成下式(8)时的纠错编码方法。

Xd^T+Yp^T＝0

Yp^T＝-Xd^T    (8)

T_lp^T＝SXd^T

式(8)的矩阵T_l是m×m矩阵，是下式(9)所示的下三角矩阵。即，在将矩 阵T_l的i行j列的元素表示成T_l(ij)时，矩阵T_l满足式(10)和式(11)。

另外，矩阵T_l只要是满足式(9)、式(10)和式(11)的m×m矩阵即可。

另外，在式(9)中，矩阵T_l的左下半部为0或者1。

T_l(ii)＝1 (1≤i≤m)   (10)

T_l(ij)＝0 (1≤i＜j≤m)   (11)

在式(8)中，矩阵S是m×m矩阵，是满足SY＝T_l的矩阵。如果对规定的矩阵 W＝[YI](其中，I表示单位矩阵)实施基本矩阵操作以使Y的部分成为T_l，则该矩阵 W成为[T_lS]，右侧部分成为S。即，该矩阵S是用于将m×m矩阵Y变换成下三角 矩阵T_l的矩阵。

该矩阵S是由基本矩阵操作部3预先计算出的。

在此，在如式(12)所示用向量u表示式(8)的最下段右边(SXd^T)时，能够 如式(13)所示计算奇偶比特序列p的第1个元素p1。并且，能够如式(14)所示 使用被称作后退代入的操作计算p1以外的元素。

SXd^T＝u^T＝(u₁，u₂，...，u_m)^T    (12)

p₁＝u₁    (13)

$p_i=u_i+\underset{j=1}{\overset{i}{\Sigma }}{T}_l\left(\mathrm{ij}\right)p_{i-1},(2\le i\le m)---\left(14\right)$

在上述基础上说明本实施方式2。图5是表示本实施方式2的纠错编码装置1的 动作的流程图。

在步骤ST21中，与上述实施方式1的步骤ST11同样，稀疏矩阵运算部2运算 信息比特序列d与奇偶校验矩阵H的m×k矩阵X的异或，得到Xd^T的向量。

在步骤ST22中，矩阵相乘部4按照上式(12)，将另行计算出的矩阵S与步骤 ST21的计算结果Xd^T相乘，得到向量u。在此，矩阵S是m×m矩阵的非稀疏矩阵。 因此，在本步骤ST22中需要计算约m×m/2次异或。

在步骤ST23中，奇偶比特计算部6按照上式(13)和上式(14)，根据在步骤 ST22中得到的向量u依次计算奇偶比特序列p的元素。本步骤ST23的运算量依赖于 矩阵T_l包含的1的个数，异或约为m×m/4次。

在前面说明的现行方法中，将矩阵Q1与信息比特序列d相乘，然后与式(13) 和式(14)同样地通过计算求出奇偶比特序列p。但是，矩阵Q1是m×k矩阵的非 稀疏矩阵。因此，需要计算约m×k/2次异或，运算量大。

另一方面，在本实施方式2中，异或的次数在步骤ST21中是比m×m次少很多 的次数，在步骤ST22中约为m×m/2次，在步骤ST23中约为m×m/4次，因而通过 合计约3×m×m/4次异或的计算，能够对LDPC码进行编码。因此，在m<k且m与 k之差大的情况下，相比现行方法的约m×k/2次，能够削减运算量。

另外，在本实施方式2中估算出的运算量的值即约3×m×m/4大于上述实施方 式1的约m×m/2。但是，这些运算量的实际值依赖于矩阵S、T_l和实施方式1的逆 矩阵Y^-1，因而具体的运算量根据即将实施的奇偶校验矩阵H而不同。并且，根据奇 偶校验矩阵H，本实施方式2中的运算量少于上述实施方式1中的运算量。在任何情 况下，与现行方法相比，都能够削减运算量。

如上所述，根据实施方式2，纠错编码装置1实施以下步骤：稀疏矩阵运算步骤， 根据奇偶校验矩阵中与信息比特序列对应的部分矩阵的1的位置，运算该部分矩阵与 信息比特序列的异或来计算向量；以及矩阵相乘步骤，将在稀疏矩阵运算步骤中得到 的向量，与对奇偶校验矩阵中与奇偶比特序列对应的部分矩阵实施了预先设定的基本 矩阵操作后的预先设定的矩阵(即，用于将奇偶校验矩阵中与奇偶比特序列对应的部 分矩阵变换成下三角矩阵T_l的矩阵S)相乘。因此，通过将奇偶校验矩阵与信息比特 序列的相乘运算分成2次进行，与现行方法相比，能够减小在相乘运算中使用的非稀 疏矩阵的尺寸。因此，能够削减对LDPC码进行编码的运算量。

另外，根据实施方式2，纠错编码装置1执行奇偶比特计算步骤，使用在矩阵相 乘步骤中得到的向量和下三角矩阵计算奇偶比特序列。因此，能够以较少的向量的相 加次数计算奇偶比特序列，能够削减对LDPC码进行编码的运算量。

另外，在实施方式2中，设矩阵T_l为下三角矩阵，但不限于此。在这种情况下， 虽然是否能够通过式(14)所示的向量的相加来实施步骤ST23，在运算量方面还是 问题，但是，能够通过向量的相加来实施步骤ST23的矩阵T_l的构造不限于下三角矩 阵。只要能够以较少的向量的相加次数构成步骤ST23，就能够以较小的运算量对 LDPC码进行编码。

作为这样的矩阵T_l的示例，有将下三角矩阵的列或者行更换而成的矩阵、或者 一部分成为下三角的矩阵。另外，当然如果将矩阵T_l设为单位矩阵，则矩阵S与m ×m矩阵Y的逆矩阵Y^-1相同，即，成为与上述实施方式1相同的结构。

在任何情况下，基本矩阵操作部3都能够与以上说明的基于基本矩阵操作的矩阵 S的计算方法同样地从矩阵T_l计算矩阵S，能够实施步骤ST22。

另外，实施方式2的步骤ST21～ST23各自的运算是比特彼此的相加和相乘，因 而与上述实施方式1同样，稀疏矩阵运算部2、矩阵相乘部4和奇偶比特计算部5分 别由如下电路构成，该电路由异或门和与门构成。

在该电路结构的情况下，通过与现行方法相比减小在相乘运算中使用的非稀疏矩 阵S的尺寸，能够削减异或的次数，其结果是，还能够削减纠错编码装置1的电路规 模。

另外，在实施方式2中，与上述实施方式1同样，说明了将码字c的向量的左侧 设为信息比特序列d，将右侧设为奇偶比特序列p的纠错编码方法，但不限于此。例 如，也可以将码字c中的任意部分设为奇偶比特序列p，在这种情况下，为了实现本 实施方式2的结构，作为一例有这样的方法，进行将码字c的元素重排的处理，使奇 偶比特序列p成为向量右侧，与此相应地也对奇偶校验矩阵H的列进行重排的处理。 即使重排奇偶校验矩阵H的列，LDPC码的本质性质也不会改变，因而能够实现这样 的方法。

另外，在实施方式2中，与上述实施方式1同样，也可以构成为预先求出对奇偶 校验矩阵进行基本矩阵操作而得到的运算结果，将运算结果作为数据保存到存储器等 存储部中，矩阵相乘部4使用该数据，或者构成为将运算结果组入矩阵相乘部4，从 而省略基本矩阵操作部3。

实施方式3

在本实施方式3中使用QC-LDPC码。QC-LDPC码是LDPC码的一种，是由循 环置换矩阵的块构成奇偶校验矩阵的LDPC码。

式(15)表示QC-LDPC码的一例。在式(15)中，设奇偶校验矩阵H的列数n 为n＝Nq，设行数为m＝Mq。即，奇偶校验矩阵H是包含X_ij、Y_ij在纵向为M个、在 横向为N个的构造。并且，设为K＝N-M。

另外，在式(15)中，i行j列(1≤i≤M、1≤j≤K)的元素X_ij和i行j列(1 ≤i≤M、1≤j≤M)的元素Y_ij分别是q×q的正方形矩阵，是循环置换矩阵或者零矩 阵。循环置换矩阵是式(16)所示的将单位矩阵循环移位而得到的矩阵。

另外，图6表示在实施方式3中使用的QC-LDPC码的一例。

在QC-LDPC码的奇偶校验矩阵H中，将与奇偶比特序列p对应的M行M列的 块中的第1列设为Z_j。

另外，在奇偶校验矩阵H的部分矩阵中示出的I表示q×q的单位矩阵。0表示q ×q的零矩阵，X_ij和Z_j是循环置换矩阵或者零矩阵。

另外，在本实施方式3中，信息比特序列d如式(17)所示，奇偶比特序列p 如式(18)所示。式(17)和式(18)的表述是以奇偶校验矩阵H的块单位表示在 上述实施方式1、2中使用的信息比特序列d和奇偶比特序列p。即，在将信息比特 序列按照每q个分成块时，d_b，i是由与第i(1≤i≤K)个块对应的q个信息数据构成 的向量。同样，p_b，i是在将奇偶比特序列按照每q个分成块时由与第i(1≤i≤M)个 块对应的q个奇偶比特构成的向量。

d_b，i＝(d_(i-1)q+1，d_(i-1)q+2，...，d_iq)    (17)

p_b，i＝(p_(i-1)q+1，p_(i-1)q+2，...，p_iq)    (18)

下面，使用式子来说明本实施方式3的LDPC码的编码方法。

首先，与上述实施方式1、2同样，根据上式(3)决定与奇偶校验矩阵H、信息 比特序列d和奇偶比特序列p有关的方程式。此时，奇偶校验矩阵H、信息比特序列 d和奇偶比特序列p在采用如在式(15)、式(17)和式(18)说明的分成块的表述 时，式(3)成为下式(19)。

在将该式(19)按照每个块展开时，对于第1行的块得到式(20)，对于第2～ M-1行的块得到式(21)，对于第M行的块得到式(22)。并且，在对于各个j将式 (20)、式(22)和式(21)全部相加时，得到式(23)。

$\underset{i=1}{\overset{K}{\Sigma }}{X}_{i1}{d}_{b,i}^T+Z_1{p}_{b,1}^T+p_{b,2}^T=0---\left(20\right)$

$\underset{i=1}{\overset{K}{\Sigma }}{X}_{\mathrm{ij}}{d}_{b,i}^T+Z_j{p}_{b,1}^T+p_{b,j}^T+p_{b,j+1}^T=0,(2\le j\le M-1)---\left(21\right)$

$\underset{i=1}{\overset{K}{\Sigma }}{X}_{\mathrm{iM}}{d}_{b,i}^T+Z_M{p}_{b,1}^T+p_{b,M}^T=0---\left(22\right)$

$\underset{j=1}{\overset{M}{\Sigma }}\left(\underset{i=1}{\overset{K}{\Sigma }}{X}_{\mathrm{ij}}{d}_{b,i}^T\right)+\underset{j=1}{\overset{M}{\Sigma }}{Z}_j{p}_{b,1}^T=0---\left(23\right)$

式(23)中包含的奇偶比特的块只有p_b，1，因而通过将式(23)变形，能够得到 式(24)，能够计算出p_b，1。

$p_{b,1}^T={\left(\underset{j=1}{\overset{M}{\Sigma }}{Z}_j\right)}^{-1}\left(\underset{j=1}{\overset{M}{\Sigma }}\left(\underset{i=1}{\overset{K}{\Sigma }}{X}_{\mathrm{ij}}{d}_{b,i}^T\right)\right)---\left(24\right)$

另外，如果对一部分j适当将式(21)和式(22)相加，则得到能够计算出针对 各个j(2≤j≤M-1)的p_b，j的式(25)，将该式(25)变形即可得到式(26)。式(26) 右边的p_b，1是根据式(24)计算出的值。另外，r表示用Σ求和的对象(j，j+1，…， M)，根据式(26)对第j个块到第M个块求出Σ内部(圆括弧内)的向量的总和。

$\underset{r=j}{\overset{M}{\Sigma }}\left(\underset{i=1}{\overset{K}{\Sigma }}{X}_{\mathrm{ir}}{d}_{b,i}^T\right)+\underset{r=j}{\overset{M}{\Sigma }}\left(Z_r{p}_{b,1}^T\right)+p_{b,j}^T=0,(2\le j\le M-1)---\left(25\right)$

$p_{b,j}^T=\underset{r=j}{\overset{M}{\Sigma }}\left(\underset{i=1}{\overset{K}{\Sigma }}{X}_{\mathrm{ir}}{d}_{b,i}^T\right)+\underset{r=j}{\overset{M}{\Sigma }}\left(Z_r{p}_{b,1}^T\right),(2\le j\le M-1)---\left(26\right)$

另外，从式(22)得到能够计算出p_b，M的式(27)，在式(27)中，与式(26) 同样通过使用从式(24)计算出的p_b，1，能够计算出p_b，M。

$p_{b,M}^T=\underset{i=1}{\overset{K}{\Sigma }}{X}_{\mathrm{iM}}{d}_{b,i}^T+Z_M{p}_{b,1}^T---\left(27\right)$

如上所述，能够计算出具有奇偶校验矩阵H的LDPC码的奇偶比特，能够对LDPC 码进行编码。

在上述基础上说明本实施方式3。

图7是表示本实施方式3的纠错编码装置1的结构的框图。本实施方式3的纠错 编码装置1具有稀疏矩阵运算部2、基本矩阵操作部3、(第一)矩阵相乘部4、奇偶 比特计算部5、向量元素相加部6和第二矩阵相乘部7。另外，在图7中对与图1及 图4相同或者相当的部分标注相同的标号，并省略说明。

图8是表示本实施方式3的纠错编码装置1的动作的流程图。

在步骤ST31中，虽然表述不同，但是与上述实施方式1、2的步骤ST11、ST21 同样，稀疏矩阵运算部2运算信息比特序列d_b，i与奇偶校验矩阵H的部分矩阵X_ij的 异或，关于X_ijd_b，i的各个j得到q维向量。本步骤ST31对应于上式(20)～(22) 的第一项的计算。X_ij表示循环置换矩阵，由于是稀疏矩阵，因而本步骤ST31的运算 量小。

在步骤ST32中，向量元素相加部6按照r＝1～j将步骤ST31的计算结果即q维 向量相加M-1次。本步骤ST32对应于上式(23)的第一项的计算。

在步骤ST33中，矩阵相乘部4按照上式(24)，将另行计算出的Z_j的j＝1～M的 总和的矩阵的逆矩阵与步骤ST32的计算结果相乘，得到奇偶比特序列p_b，1。其中， Z_j的总和的逆矩阵由基本矩阵操作部3预先计算出。该逆矩阵虽然不是稀疏矩阵，却 是q×q矩阵，矩阵尺寸小。因此，本步骤ST33的运算量小。

在步骤ST34中，第二矩阵相乘部7计算针对在步骤ST33中得到的奇偶比特序 列p_b，1的各个Z_j的相乘运算、与作为其相乘结果的向量之和。本步骤ST34对应于上 式(25)的第二项的计算。另外，Z_j是稀疏矩阵，运算量小。

在步骤ST35中，奇偶比特计算部5按照上式(26)和上式(27)，将步骤ST32 的计算结果和步骤ST34的计算结果相加，计算出奇偶比特序列p_b，j、p_b，M。本步骤 ST35是2个向量的相加运算，因而运算量小。

在本实施方式3中，通过减少使用非稀疏矩阵的运算，实现运算量的削减。非稀 疏矩阵是针对步骤ST33的Z_j的j的总和的逆矩阵，但该逆矩阵是q×q矩阵，尺寸 较小。作为标准，与在上述实施方式1、2及现行方法中使用的非稀疏矩阵尺寸的m 和k相比，q通常小至1/3～1/100。因此，步骤ST33的运算量成为约q×q/2次的异 或，与现行方法相比，能够以q/m或者q/k的平方量级削减运算量。

另外，在步骤ST33以外的步骤中运算量有可能最多的是步骤ST31，但在步骤 ST31中使用的矩阵X是稀疏的，并且步骤ST31是与上述实施方式1、2的步骤ST11、 ST21相同的运算。因此，只要是相同的奇偶校验矩阵，则本实施方式3的编码方法 与上述实施方式1、2的编码方法相比能够削减运算量。

如上所述，根据实施方式3，纠错编码装置1构成为实施以下步骤：稀疏矩阵运 算步骤，根据奇偶校验矩阵中与信息比特序列对应的部分矩阵的1的位置，运算该部 分矩阵与信息比特序列的异或来计算向量；向量元素相加步骤，将在稀疏矩阵运算步 骤中得到的向量的元素的一部分相加；(第一)矩阵相乘步骤，将在向量元素相加步 骤中得到的向量，与将奇偶校验矩阵中与奇偶比特序列对应的部分矩阵的一部分相加 而得到的矩阵的逆矩阵相乘，计算奇偶比特序列的一部分；第二矩阵相乘步骤，将在 (第一)矩阵相乘步骤中得到的奇偶比特序列的一部分，与奇偶校验矩阵中与奇偶比 特序列对应的部分矩阵的剩余部分相乘；以及奇偶比特计算步骤，将在向量元素相加 步骤中得到的向量和在第二矩阵相乘步骤中得到的向量相加，计算奇偶比特序列的剩 余部分。因此，在QC-LDPC码的编码处理中，许多运算能够使用稀疏矩阵进行，能 够削减运算量。并且，与上述实施方式1、2同样，与现行方法相比，能够减小在相 乘运算中使用的非稀疏的逆矩阵的尺寸，由此，还能够削减运算量。

另外，实施方式3的步骤ST31～ST35各自的运算是比特彼此的相加和相乘，因 而与上述实施方式1、2同样，稀疏矩阵运算部2、矩阵相乘部4、第二矩阵相乘部7 以及奇偶比特计算部5分别由如下电路构成，该电路由异或门和与门构成。

在该电路结构中，通过使在相乘运算中使用的非稀疏的逆矩阵的尺寸小于现行方 法，能够削减异或的次数，其结果是，还能够削减纠错编码装置1的电路规模。

另外，与上述实施方式1、2同样，在实施方式3中说明的纠错编码方法也是将 码字c的向量的左侧设为信息比特序列d，将右侧设为奇偶比特序列p，但不限于此。 例如，也可以将码字c中的任意部分设为奇偶比特序列p，在这种情况下，为了实现 本实施方式3的结构，作为一例有这样的方法，进行将码字c的元素重排的处理，使 奇偶比特序列p成为向量右侧，与此相应地还对奇偶校验矩阵H的列进行重排的处 理。即使重排奇偶校验矩阵H的列，LDPC码的本质性质也不会改变，因而能够实现 这样的方法。

另外，与上述实施方式1、2同样，在实施方式3中也可以构成为预先求出对奇 偶校验矩阵进行基本矩阵操作而得到的运算结果，将运算结果作为数据保存到存储器 等存储部中，矩阵相乘部4使用该数据，或者构成为将运算结果组入矩阵相乘部4， 从而省略基本矩阵操作部3。

实施方式4

图9是表示本发明的实施方式4的纠错编码装置1的结构的框图。本实施方式4 的纠错编码装置1具有稀疏矩阵运算部2、基本矩阵操作部3、矩阵相乘部4、奇偶 比特计算部5、向量元素相加部6、第二矩阵相乘部7、循环移位部8、9和逆循环移 位部10。另外，在图9中对与图7相同或者相当的部分标注相同的标号，并省略说 明。

在本实施方式4中，利用基于基本矩阵操作的其它表述来说明在上述实施方式3 中说明的奇偶比特序列p的计算式。

如已经说明的那样，应用上述实施方式3的QC-LDPC码的奇偶校验矩阵H的一 例如图6所示。图6的奇偶校验矩阵H通过基本矩阵操作部3进行的规定的基本矩 阵操作而成为简单的构造。图10是说明该基本矩阵操作的图，按照箭头上侧所示， 对于奇偶校验矩阵H，按照块单位顺序地进行相加运算(1)～相加运算(M-1)，即 形成箭头下侧的矩阵。可知通过该基本矩阵操作能够使单位矩阵I消失许多，如果将 在第1行出现的Z_r的r＝1～M的总和除外，则形成下三角矩阵的构造。该Z_r的总和 与在图8的步骤ST33和上式(24)中被用作逆矩阵的Z_j的总和的q×q矩阵对应。

在上述基础上，可知奇偶校验矩阵H不限于图6的构造。

因此，在本实施方式4中，作为一例是使用图11所示的奇偶校验矩阵H。图11 所示的奇偶校验矩阵H是在图6的奇偶校验矩阵H中，用循环置换矩阵A_j置换作为 单位矩阵I的部分的一部分或者全部而形成的构造。并且，也可以使A_j的一部分或 者全部成为零矩阵。

即，关于图10所示的相加运算(j)(1≤j≤M-1)，基本矩阵操作部3不是单纯 地按照块单位进行相加，而是在图11的情况下，首先，循环移位部8使要相加的2 个块(例如，奇偶校验矩阵H的最下面第M行的块和其上面一行的第M-1行的块) 中下方的块X_ij、Z_j、A_j循环移位，然后，基本矩阵操作部3将循环移位后的下方的 块与上方的块相加。反复进行该动作，即可得到与图10的箭头下侧的矩阵相同的矩 阵。

在这种情况下得到的矩阵是图10的箭头下侧的矩阵中的将一部分部分矩阵X_ij、 Z_j循环移位后的构造。图10所示的I和0的部分保持与图10相同的状态。

基本矩阵操作部3将通过循环移位部8使X_ij、Z_j、A_j循环移位后的奇偶校验矩 阵H的各行相加(j)，然后计算在第1行出现的Z_r的r＝1～M的总和的逆矩阵，将该 逆矩阵输出给矩阵相乘部4。

通过按照以上所述使奇偶校验矩阵H的部分矩阵循环移位并进行基本矩阵操作， 能够得到与图10的箭头下侧的矩阵相同的矩阵，但是，还需要与此时的循环移位对 应地使信息比特序列d和奇偶比特序列p循环移位。

具体而言，循环移位部9在执行图8的步骤ST31之前，使信息比特序列d按照 局部向量d_b，i单位循环移位。另一方面，逆循环移位部10在执行了图8的步骤ST35 之后，使奇偶比特序列p按照局部向量p_b，i单位循环移位。循环移位部9和逆循环移 位部10进行的循环移位对应于循环移位部8进行的块X_ij、Z_j、A_j的循环移位，循环 移位部9对信息比特序列d_b，i执行与循环移位部8对奇偶校验矩阵H的各X_ij实施的 循环移位相同的循环移位，使信息比特序列d_b，i移位。并且，逆循环移位部10对奇 偶比特序列p_b，i执行与循环移位部8对奇偶校验矩阵H的各Z_j、A_j实施的循环移位 相反的移位，使奇偶比特序列p_b，i恢复原状。

通过以上的处理，在本实施方式4的纠错编码装置1中也能够执行与图8相同的 编码方法。

如上所述，根据实施方式4，在纠错编码装置1中，奇偶校验矩阵由与信息比特 序列对应的部分矩阵X_ij(i表示行，j表示列)、与奇偶比特序列对应的部分矩阵中第 1列的部分矩阵Z_j和第2列以后的部分矩阵构成，该第2列以后的部分矩阵采用在构 成为对角成分包含循环置换矩阵A_j且在该循环置换矩阵A_j各自的下方紧接着包含单 位矩阵的矩阵中，构成为由循环移位部8使部分矩阵X_ij、Z_j和循环置换矩阵A_j的一 部分循环移位后的矩阵。因此，通过对图11所示构造的奇偶校验矩阵H使一部分部 分矩阵循环移位，能够利用图8的编码方法对LDPC码进行编码。即使使一部分部分 矩阵循环移位，矩阵中包含的1的个数也不变，因而形成与上述实施方式3的图6 所示构造的奇偶校验矩阵H相同的运算量。因此，与现行方法和上述实施方式1、2 的编码方法相比，能够削减运算量。

另外，能够在本实施方式4中应用的奇偶校验矩阵H不限于图11。

例如，也可以如图12所示，将图11的奇偶校验矩阵H中作为单位矩阵I的部分 的一部分或者全部设为循环置换矩阵B_j。并且，也可以将B_j的一部分或者全部设为 零矩阵。因为奇偶校验矩阵H即使更换行的顺序，奇偶校验矩阵和LDPC码的本质 构造也不会改变。当然，即使使行按照块单位循环移位，本质构造也不会改变。另外， 在图12所示的奇偶校验矩阵H的行中，在按照块单位将各循环置换矩阵B_j设为单位 矩阵I的情况下，将成为与图11相同构造的奇偶校验矩阵H。

在图12的情况下，首先，循环移位部8使要相加的2个块中下方的块X_ij、Z_j、 A_j、B_j循环移位，然后，基本矩阵操作部3将循环移位后的下方的块与上方的块相加。 反复进行该动作，即可得到与图10的箭头下侧的矩阵相同的矩阵。

在这种情况下得到的矩阵是使图10的箭头下侧的矩阵中的被置换成一部分部分 矩阵X_ij、Z_j、A_j的I循环移位而得到的构造。基本矩阵操作部3将通过循环移位部8 使X_ij、Z_j、A_j、B_j循环移位后的奇偶校验矩阵H的各行相加(j)，然后计算在第1 行出现的Zr的r＝1～M的总和的逆矩阵，将该矩阵输出给矩阵相乘部4。

并且，在这种情况下，循环移位部9与循环移位部8同样地使信息比特序列d 按照局部向量d_b，i单位循环移位，逆循环移位部10与循环移位部8相反地使奇偶比 特序列p按照局部向量p_b，i单位循环移位。

通过以上处理，能够执行与图8相同的编码方法。

如上所述，根据实施方式4，在纠错编码装置1中，奇偶校验矩阵由与信息比特 序列对应的部分矩阵X_ij(i表示行，j表示列)、与奇偶比特序列对应的部分矩阵中第 1列的部分矩阵Z_j和第2列以后的部分矩阵构成，该第2列以后的部分矩阵采用在构 成为对角成分包含循环置换矩阵A_j且在该循环置换矩阵A_j各自的下方紧接着包含循 环置换矩阵B_j的矩阵中，构成为由循环移位部8使部分矩阵X_ij、Z_j和循环置换矩阵 A_j、B_j的一部分循环移位后的矩阵。因此，通过对图12所示构造的奇偶校验矩阵H 使一部分部分矩阵循环移位，能够利用图8的编码方法对LDPC码进行编码。即使使 一部分部分矩阵循环移位，矩阵中包含的1的个数也不变，因而形成与上述实施方式 3的图6所示构造的奇偶校验矩阵H相同的运算量。因此，与现行方法和上述实施方 式1、2的编码方法相比，能够削减运算量。

另外，与上述实施方式3同样，在实施方式4中，图8的步骤ST31～ST35各自 的运算也是比特彼此的相加和相乘，因而与上述实施方式3相同，稀疏矩阵运算部2、 矩阵相乘部4、第二矩阵相乘部7和奇偶比特计算部5分别由如下电路构成，该电路 由异或门和与门构成。

在该电路结构中，通过使在相乘运算中使用的非稀疏的逆矩阵的尺寸小于现行方 法，能够削减异或的次数，其结果是，还能够削减纠错编码装置1的电路规模。

另外，与上述实施方式1～3同样，在实施方式4中说明的纠错编码方法将码字 c的向量的左侧设为信息比特序列d，将右侧设为奇偶比特序列p，但不限于此。例 如，也可以将码字c中的任意部分设为奇偶比特序列p，在这种情况下，为了实现本 实施方式4的结构，作为一例有这样的方法，进行将码字c的元素按照块单位重排的 处理，使奇偶比特序列p成为向量右侧，与此相应地还对奇偶校验矩阵H的块列进 行重排的处理。如果重排后的奇偶校验矩阵H成为图11、图12示例的构造，则实施 方式4即可实施。即，可以说，如果通过按照块单位重排行和列，得到成为能够实施 以上说明的实施方式4的构造的奇偶校验矩阵H，则实施方式4即可实施。

另外，与上述实施方式1～3同样，在实施方式4中也可以构成为预先求出对奇 偶校验矩阵进行基本矩阵操作而得到的运算结果，将运算结果作为数据保存到存储器 等存储部中，矩阵相乘部4使用该数据，或者构成为将运算结果组入矩阵相乘部4， 从而省略基本矩阵操作部3。

另外，在实施方式4中，循环移位是更换数据顺序的处理，因而如果预先判明循 环移位的规则(循环移位部8的输出结果)，则能够预先求出对奇偶校验矩阵进行循 环移位和基本矩阵操作而得到的运算结果，在这种情况下，能够省略循环移位部8 和基本矩阵操作部3。

另外，如果预先判明循环移位的规则，则存在不需要安装构成循环移位部9和逆 循环移位部10的运算器等的情况。尤其是在电路的情况下，数据的顺序是根据布线 的连接方式决定的，因而不需要安装运算器，能够在不增大电路规模的情况下实现循 环移位部9和逆循环移位部10的功能。

另外，本发明能够在本发明的范围内进行各实施方式的自由组合、或者各实施方 式的任意构成要素的变形、或者在各实施方式中省略任意的构成要素。

产业上的可利用性

如上所述，本发明的纠错编码装置适合用于依据LDPC码对信息数据进行编码的 通信系统的发送设备等。

标号说明

1纠错编码装置；2稀疏矩阵运算部；3基本矩阵操作部；4(第一)矩阵相乘部； 5奇偶比特计算部；6向量元素相加部；7第二矩阵相乘部；8、9循环移位部；10逆 循环移位部。