一种具有前向纠删功能的面向字的编译码方法

技术领域

本发明属于通信技术领域，特别是涉及一种具有前向纠删功能的面向字的编译码方法。

背景技术

在卫星通信、深井、深海等依赖于通信协议的单向通信信道上传输数据时，由于信道质量问题，往往会出现信息字的随机丢失。根据相应的通信协议：(1)人们可以确保已收到的数据一定是正确的；(2)人们可以获知具体字丢失的位置，但是无法确定字丢失的具体内容；

此时，如何去对原始数据进行纠删编码，使得编码之后的数据具备一定的抗丢字能力，是提升单向通信可靠性的重要途径之一。

目前常用的办法是使用纠错编码或RS码来解决丢字问题。

纠错编码能够用来纠正数据传输错误，但是需要指出，纠错编码所能够解决的“传输错误”可以是数据的丢失，也可以是数据的内容出错，从理论上来说，传统的纠错编码并不是为了解决本应用场景下的丢字问题而量身定制的技术。因此对于“数据丢失”这一特定错误类型，其纠错效果并不理想。

RS码则是一类有效的纠删码，也是目前应用最为广泛的纠删码。但是缺陷在于:1.编译码方法复杂，需要较深的数学知识背景，其原理不易被工程人员掌握；2.RS码的编码过程中，一旦码元的比特长度确定之后，其码长就只能取固定的值，且不能根据需要做出更改，导致编码灵活性受限。

发明内容

针对现有技术中存在的缺陷，本发明提供了一种具有前向纠删功能的面向字的编译码方法，编码灵活，纠删效果好。

为了实现上述目的，本发明采用以下的技术方案：

本发明提供了一种具有前向纠删功能的面向字的编译码方法，包含以下步骤：

根据编码特性生成系统码编码矩阵；

生成解码表；

依据系统码编码矩阵完成数据编码，将每组包含n个字的原始信息组扩展成2n个字的编码信息组；

依据解码表完成译码，将2n个字所构成的编码信息组还原成原始信息组，即在编码信息组中的2n个字中，任意不超过n个字丢失，将原始信息组正确地恢复出来。

优选地，所述根据编码特性生成系统码编码矩阵包括：

输入编码的每组信息所包含的字个数为n，输入每个字长为m-bit；

寻找系数取自二元有限域GF(2)的m次不可约多项式f(x)，则根据代数理论，模f(x)的剩余类环，记作GF(2)[x]/<f(x)>，构成有限域GF(2^m)；

在有限域GF(2^m)上寻找2n个互不相同元素a₁,a₂,…,a_n,b₁,b₂,…,b_n；

在有限域GF(2^m)上寻找任意非0元素c₀，当1≤i,j≤n时，定义

定义矩阵B＝(b_i,j)_n×2n，这里的

矩阵B作为编码矩阵。

优选地，所述生成解码表包括：

对消息从0遍历至2^mn-1，对每次遍历到的值(m₁,m₂,…,m_n)，计算2n维向量

将表T的第(m₁,…,m_n)个索引值对应条目置α，即

T[(m₁,m₂,…,m_n)]＝α；

待消息值遍历完成后，T作为解码表。

优选地，所述依据系统码编码矩阵完成数据编码包括：

输入是：(1)编码矩阵B；(2)待编码的、由n个字所构成的原始信息组Message＝(m₁,m₂,…,m_n)；

输出是：编码之后的，由2n个字所构成的编码信息组Encoded_M＝(e₁,e₂,…,e_2n)；

由原始信息组向编码信息组变换的计算公式是：Encoded_M＝Message×B；即对1≤i≤2n，均有

Encoded_M作为编码后的数据组进入信道发送。

优选地，所述依据解码表完成译码包括：

输入是：接收到的数据组Encoded_M′＝(e′₁,e′₂,…,e′_2n)；

输出是：原始数据Message；

对1≤i≤2n，依次查看e′_i是否丢失，若丢失，令θ_i＝0，否则令θ_i＝1，由此生成错位向量θ＝(θ₁,θ₂,…,θ_2n)；

对1≤i≤2n，判断：若θ_i＝0，则令d_i＝0；若θ_i＝1，则令d_i＝e′_i，由此生成查询向量D＝(d₁,d₂,…,d_2n)；

判断：若θ₁＝θ₂＝…＝θ_n＝1，则直接返回Message＝(e′₁,e′₂,…,e′_n)，过程结束；否则执行下面的步骤；

在解码表T中，对条目做遍历，抽取当前遍历的条目

T[k]＝(α₁,α₂,…,α_2n)；

构造向量TEMP＝(temp₁,temp₂,…,temp_2n)，这里的

判断D&TEMP是否为全0向量，这里的操作“&”表示逐位与运算；若是，则取出T[k]＝(α₁,α₂,…,α_2n)的前n个分量，并输出译码值Message＝(α₁,α₂,…,α_n)，译码结束；否则，进行下一次抽取当前遍历的条目。

与现有技术相比，本发明具有以下优点：

本发明提供了一种具有前向纠删功能的面向字的编译码方法，本质上是一种专门解决数据丢失的专用纠错编码，对于单组数据，能够在最多50％字块丢失的前提下正确还原原始消息。同时，本发明的编码矩阵生成快捷，编译码算法易于实现，码长受码元所在的有限域规模的制约程度小，具有很好的环境适应性。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本发明实施例提供的一种具有前向纠删功能的面向字的编译码方法的工作流程图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

为了使本领域的技术人员更好地理解本发明方案，下面结合附图和具体实施方式对本发明作进一步的详细说明。

实施例一

请参照图1，图1为本发明实施例提供的一种具有前向纠删功能的面向字的编译码方法的工作流程图，该方法包含：

步骤1，根据编码特性生成系统码编码矩阵；

步骤2，生成解码表；

步骤3，依据系统码编码矩阵完成数据编码，假设待编码的每组信息均由n个字构成，每个字长为m-bit，将每组包含n个字的原始信息组扩展成2n个字的编码信息组；

步骤4，依据解码表完成译码，将2n个字所构成的编码信息组还原成原始信息组，即在编码信息组中的2n个字中，任意不超过n个字丢失，均可将原始信息组正确地恢复出来。

作为优选地，所述根据编码特性生成系统码编码矩阵包括：

步骤S101，输入编码的每组信息所包含的字个数为n，输入每个字长为m-bit；

步骤S102，寻找系数取自二元有限域GF(2)的m次不可约多项式f(x)，则根据代数理论，模f(x)的剩余类环，记作GF(2)[x]/<f(x)>，构成有限域GF(2^m)；

步骤S103，在有限域GF(2^m)上寻找2n个互不相同元素a₁,a₂,…,a_n,b₁,b₂,…,b_n；

步骤S104，在有限域GF(2^m)上寻找任意非0元素c₀，当1≤i,j≤n时，定义

步骤S105，定义矩阵B＝(b_i,j)_n×2n，这里的

矩阵B作为编码矩阵。

作为优选地，所述生成解码表包括：以步骤1的编码矩阵B为输入，通过依次执行以下步骤生成解码表T。

步骤S201，对消息从0遍历至2^mn-1，对每次遍历到的值(m₁,m₂,…,m_n)，计算2n维向量

步骤S202，将表T的第(m₁,…,m_n)个索引值对应条目置α，即

T[(m₁,m₂,…,m_n)]＝α；

步骤S203，待消息值遍历完成后，T作为解码表。

作为优选地，所述依据系统码编码矩阵完成数据编码包括：

输入是：(1)步骤1所生成的编码矩阵B；(2)待编码的、由n个字所构成的原始信息组Message＝(m₁,m₂,…,m_n)；

输出是：编码之后的，由2n个字所构成的编码信息组Encoded_M＝(e₁,e₂,…,e_2n)；

步骤S301，计算Encoded_M＝Message×B；即对1≤i≤2n，均有

步骤S302，Encoded_M作为编码后的数据组进入信道发送。

作为优选地，所述依据解码表完成译码包括：

输入是：接收到的数据组Encoded_M′＝(e′₁,e′₂,…,e′_2n)；

输出是：原始数据Message；

步骤S401，对1≤i≤2n，依次查看e′_i是否丢失，若丢失，令θ_i＝0，否则令θ_i＝1，由此生成错位向量θ＝(θ₁,θ₂,…,θ_2n)；

步骤S402，对1≤i≤2n，判断：若θ_i＝0，则令d_i＝0；若θ_i＝1，则令d_i＝e′_i，由此生成查询向量D＝(d₁,d₂,…,d_2n)；

步骤S403，判断：若θ₁＝θ₂＝…＝θ_n＝1，则直接返回Message＝(e′₁,e′₂,…,e′_n)，过程结束；否则执行下面的步骤；

步骤S404，在解码表T中，对条目做遍历，抽取当前遍历的条目

T[k]＝(α₁,α₂,…,α_2n)；

步骤S405，构造向量TEMP＝(temp₁,temp₂,…,temp_2n)，这里的

步骤S406，判断D&TEMP是否为全0向量，这里的操作“&”表示逐位与运算；若是，则取出T[k]＝(α₁,α₂,…,α_2n)的前n个分量，并输出译码值Message＝(α₁,α₂,…,α_n)，译码结束；否则，返回步骤S404进行下一次抽取。

本发明提供的具有前向纠删功能的面向字的编译码方法是一种专门解决数据丢失的专用纠错编码，对于单组数据，能够在最多50％字块丢失的前提下正确还原原始消息，纠删效果好；本发明还提出了系统码编码矩阵的高效设计方案，能够根据编码参数的不同灵活选择编码矩阵的大小，编码矩阵生成快捷，编译码算法易于实现，对使用者和程序编写者的数学基础要求不高，码长受码元所在的有限域规模的制约程度小，具有很好的环境适应性。

下面举一个具体地实例，以便于更好地理解本发明。

实施例二

步骤1，根据编码特性生成系统码编码矩阵；

步骤S101，输入编码的每组信息所包含的字个数为4，输入每个字长为4-bit；

步骤S102，构造有限域GF(2⁴)＝GF(2)[x]/<x⁴+x+1>；

步骤S103，在有限域GF(2⁴)上寻找8个互不相同元素

a₁＝1,a₂＝2,a₃＝3,a₄＝4,b₁＝5,b₂＝6,b₃＝7,b₄＝8；

步骤S104，在有限域GF(2⁴)上寻找非0元素c₀＝2，当1≤i,j≤4时，定义

步骤S105，定义矩阵B＝(b_i,j)_4×8，这里的

即

矩阵B作为编码矩阵。

步骤2，以步骤1的编码矩阵B为输入，通过依次执行以下步骤生成解码表T；

步骤S201，对消息从0遍历至2¹⁶-1，对每次遍历到的值(m₁,m₂,m₃,m₄)，计算8维向量

步骤S202，将表T的第(m₁,m₂,m₃,m₄)个索引值对应条目置α，即

T[(m₁,m₂,m₃,m₄)]＝α；

步骤S203，待消息值遍历完成后，T作为解码表。

在上面生成的T值表中，例如我们想计算T[1]的值，那么输入1可以表示成(m₁,m₂,m₃,m₄)＝(0,0,0,1)，此时根据步骤S201计算有

α＝[(1×b_4,1),(1×b_4,2),…,(1×b_4,8)]＝(0,0,0,1,2,1,15,7)，

根据步骤S202，即可知T[1]的取值就是(0,0,0,1,2,1,15,7)。

步骤3，完成数据编码过程；

输入是：(1)步骤1所生成的编码矩阵B；(2)待编码的、由4个字所构成的原始信息组Message＝(m₁,m₂,m₃,m₄)；

输出是：编码之后的，由8个字所构成的编码信息组

Encoded_M＝(e₁,e₂,e₃,e₄,e₅,e₆,e₇,e₈)；

步骤S301，计算Encoded_M＝Message×B；即对1≤i≤8，均有

步骤S302，Encoded_M作为编码后的数据组进入信道发送。

假设在步骤3中，待编码的数据为Message＝(0,0,0,1)，那么经执行步骤3后，编码数据为Encoded_M＝Message×B＝(0,0,0,1,2,1,15,7)。

步骤4，基于步骤2所给出的解码表T完成译码过程；

输入是：接收到的数据组Encoded_M′＝(e′₁,e′₂,e′₃,e′₄,e′₅,e′₆,e′₇,e′₈)；

输出是：原始数据Message；

我们假设由于信道原因，导致接收方接收到的编码数据为Encoded_M′＝(？,？,0,1,？,1,15,？)，这里的？表示该位置的信号有丢失。

步骤S401，对1≤i≤8，依次查看e′_i是否丢失，若丢失，令θ_i＝0，否则令θ_i＝1，由此生成错位向量θ＝(θ₁,θ₂,…,θ₈)；

收方根据步骤S401构造错位向量θ＝(0,0,1,1,0,1,1,0)；

步骤S402，对1≤i≤8，判断：若θ_i＝0，则令d_i＝0；若θ_i＝1，则令d_i＝e′_i，由此生成查询向量D＝(d₁,d₂,…,d₈)；

收方再根据步骤S402生成查询向量D＝(0,0,0,1,0,1,15,0)；

步骤S403，判断：若θ₁＝θ₂＝…＝θ₄＝1，则直接返回Message＝(e′₁,e′₂,…,e′₈)，过程结束；否则执行下面的步骤；

收方执行步骤S403，判断不符合终止条件，执行步骤S404；

步骤S404，在解码表T中，对条目做遍历，抽取当前遍历的条目

T[k]＝(α₁,α₂,…,α₈)；

收方执行步骤S404，直至抽取T[1]＝(0,0,0,1,2,1,15,7)；

步骤S405，构造向量TEMP＝(temp₁,temp₂,…,temp₈)，这里的

收方执行步骤S405，构造了TEMP＝(0,0,0,1,0,1,15,0)；

步骤S406，判断D&TEMP是否为全0向量，这里的操作“&”表示逐位与运算；

若是，则从T[k]中取出分量(α₁,α₂,α₃,α₄)，并作为译码值输出，译码结束；

否则，返回步骤S404进行下一次抽取。

收方执行步骤S406，计算并判定D&TEMP＝＝0，故从T[1]中取出分量(0,0,0,1)，并作为译码值输出，该步数据译码结束。

最后应说明的是：以上所述实施例，仅为本发明的具体实施方式，用以说明本发明的技术方案，而非对其限制，本发明的保护范围并不局限于此，尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，其依然可以对前述实施例所记载的技术方案进行修改或可轻易想到变化，或者对其中部分技术特征进行等同替换；而这些修改、变化或者替换，并不使相应技术方案的本质脱离本发明实施例技术方案的精神和范围，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应所述以权利要求的保护范围为准。