一种基于有限域的多进制喷泉编码和译码方法

摘要

本发明涉及一种基于有限域的多进制喷泉编码和译码方法。首先对喷泉码进行编码，得到喷泉编码序列：给定编码度分布函数μ(d)，根据分布函数μ(d)随机生成一个非负整数d_i，将d_i作为编码符号v_i的编码度；从K个信源符号中随机选取d_i个不同的符号；从有限域GF(q)中随机均匀产生d_i个非零值作为编码符号v_i的编码系数；根据编码系数对d_i个不同的符号求加权和，得到编码符号v_i的值，进而得到喷泉编码序列。从该喷泉编码序列中选取出长度为N(N≥K)的编码序列，记为w＝[w₁，w₂，…，w_N]^T，通过主元选择和主元原位高斯消元，对其进行译码，得到最终的译码输出序列。本发明方法极大地提高了喷泉编码的编码效率，降低了喷泉码的译码复杂度，适合于各种信源长度的喷泉码应用。

主权项

1、一种基于有限域的多进制喷泉编码和译码方法，其特征在于，包括以下步骤：定义GF(q)表示有限域，即伽罗华域，q是任意素数或者素数的正整数次幂；一个定义于有限域GF(q)的矩阵或矢量，称其非零元素的个数为该矩阵或矢量的重量；令v_∞＝[v₁，v₂，…]表示长度半无限的喷泉编码序列，一个编码符号v_i(i＝1，2，…)的编码度表示参加该符号编码的信源符号个数；设信源的长度为K；令m＝[m₁，m₂，…，m_K]^T表示信源矢量，其第j个符号取自于GF(q)，j＝1，2，…，K；步骤一、对喷泉码进行编码，得到喷泉编码序列v_∞＝[v₁，v₂，…]；其中，编码符号v_i(i＝1，2，…)的实现步骤如下：首先，给定编码度分布函数μ(d)，根据分布函数μ(d)随机生成一个非负整数d_i，将d_i作为编码符号v_i的编码度；然后，从K个信源符号中随机选取d_i个不同的符号，记为所选择符号的序号集合；之后，从有限域GF(q)中随机产生d_i个非零值作为编码符号v_i的编码系数，记这些编码系数构成的集合为$C=\{c_1,c_2,···,c_{d_i}\};$最后，根据编码系数对d_i个不同的符号求加权和，得到编码符号v_i的值，即，使用公式$v_i=c_1·m_{s_1}+c_2·m_{s_2}+···+c_{d_i}·m_{s_{d_i}}$计算编码符号v_i的值；步骤二、从v_∞＝[v₁，v₂，…]中选取出长度为N(N≥K)的编码序列，记为w＝[w₁，w₂，…，w_N]^T，对该喷泉编码序列进行译码，得到原信源序列，实现过程如下：设接收机向译码器输入长度为N(N≥K)的编码序列w＝[w₁，w₂，…，w_N]^T，将编码序列w＝[w₁，w₂，…，w_N]^T表示为信源序列的线性组合，即，线性方程组w＝A·m，其中，A是一个N×K阶矩阵，其元素取自于GF(q)，线性方程组w＝A·m的加法和乘法元素是定义于有限域GF(q)的运算；利用矩阵A的稀疏特性，对喷泉编码序列w＝[w₁，w₂，…，w_N]^T进行译码，过程如下：(1)对矩阵A进行主元选择对于矩阵为A的有限长喷泉编码序列w＝[w₁，w₂，…，w_N]^T，高斯消元法的前向消元过程共有K步，在前向过程的第k(k＝1，2，…，K)步，矩阵的第k行除以其(k，k)位置的元素，然后分别将该行各适当倍数与下面的各行相加，使下面各行第k列的非零元素全都变成零，当前向过程的第k步完成时，矩阵被化为上三角形式，$A^{\left(k\right)}=\left[a_{i,j}^{\left(k\right)}\right]$为第k步开始时的矩阵，A⁽¹⁾＝A为原始的矩阵，矩阵A^(k)的前k-1列即为上三角矩阵，是待消元的剩余矩阵；在前向消去的每一步，在剩余矩阵中，选取最大填入和操作数最小的元素作为主元；剩余矩阵共有N-k+1行和K-k+1列，设是的非零元，i∈{1，…，N-k+1}，j∈{1，…，K-k+1}，则为一个候选主元；令r_i和c_j分别表示剩余矩阵第i行和第j列的重量，数值(r_i-1)·(c_j-1)为选择度量；使用局部填充元和局部操作数最小化的主元选择策略，在前向消去的第k步，选取剩余矩阵中最小选择度量的元作为第k步时的主元；(2)对矩阵A进行主元原位高斯消元定义B^(k)＝[A^(k)|w^(k)]为高斯消去前向过程第k步开始时的增广矩阵，则其线性方程组的系数矩阵化为A^(k)，编码矢量化为w^(k)，其中A⁽¹⁾＝A表示初始编码矩阵，w⁽¹⁾＝w表示输入到译码器的编码矢量；a)令计数器的步数k＝1；b)设主元为记录第k步的主元行号和列号，即标记S_k(i_k，j_k)，以主元除以第i_k个方程中剩下的未知数的非零系数和右端项，而后，从所有未选过主元的方程中消去第j_k个未知数；c)若k<K，设置k＝k+1，重复b)，直至k＝K；最后，采用后向迭代，求解线性方程组w＝A·m中的未知量m的元素即$m_{j_k}=v_{i_k}^{\left(k\right)}-\underset{s\in \{k+1,···,K\},a_{i_k,j_s}^{\left(k\right)}\ne 0}{\Sigma }{a}_{i_k,j_s}^{\left(k\right)}{m}_{j_s}$其中，k＝1，2，…，K，由此得到译码输出序列m。