基于快速傅里叶变换的多元LDPC译码算法FFT-QSPA
这个文章讲解一下多元 LDPC 码的一种译码算法：基于 FFT 的译码算法。
所谓的多元，是指参与运算的数据不是比特，而是有更多的取值，例如取值0，1，2，3，或者例如取值01,2,3,4,5 等等。 校验矩阵的系数也是可以取值不只是 0 和 1 ，例如下面这个校验矩阵，是以模 4 运算为基础的校验矩阵，也就是很多教科书中称之为有限域 , 当然涉及到很多高等代数的知识，但是，在这里，就都理解为模 4 的运算即可，无论加减乘，最后的结果都模 4 运算即可。
所以，这里面有三个校验方程，收到 6 个数（记为 ），LDPC 编码后的数据有六个，记为
， 三个校验方程可以写为：
特别提醒，上面的运算都是在模 4 的规则下的，计算的结果都需要做模 4 运算。
本来最优的译码方法是找 中概率最大的，把概率最大时对应的
作为我们的译码结果。但是，这个运算量大，当码长较长时，运算量大到不可行。我们退而求其次，计算单个
的概率来做判决：
我们把上面的公式做一些进一步的推导：
其中，（因为这个条件中没有约束方程的要求，因此，其他的
就不影响
.
公式 (1) 中，我们为了简化运算，我们假设各个校验方程的成立与否，是相互独立的，当然，实际上由于每个发送的数据，都参与多个校验方程，因此，校验方程之间是有相互关联的，这里的假设，导致了一个约等于：
我们举个例子，例如 在开头的校验方程中，我们考虑译码 则
现在，我们已经用校验方程成立与否的概率，来表示了发送数据的概率。
接着对公式 (2) 中的 进行一些推导：
其中 ，可以认为是一个常数，我们来分析分子的部分, 因为
给定，那么
的话，就意味着校验方程中其他项要取各种情况
其中
则公式 (4) 变成：
我们举个例子，例如校验方程 ， 以
为例子
则有下列一些情况：
针对上面任何一种情况，例如
从上面的举例中也可以看出，计算公式 (4) 是非常复杂的，运算量非常大。而且，我们还需要计算 等于其他三种值(0,1,2)的情况，可见，公式(4) 和公式 (5) 的计算量之大。
这里，引入一种在模 4 这种操作下的傅里叶变换，这里我们不做严格的证明，只是把这个思想和过程梳理一下，理解了这是在干啥，后面可以查阅更专业的书籍和文献，来看严格的证明。
我们举一个二元码的例子，即取值只有 0 和 1， 有两个随机变量，，令：
如果我们要计算：
和
那么公式 (6) 可以展开为：
公式(7) 可以展开为：
对于这种二元的情况，我们引入一种变换：
因为是二元的情况，所以，这个变换是对某个随机变量的两种取值的概率的变换，对 做变换：
对 做变换
对上面两种变换之后的结果，即两个列向量，做对应元素相乘：
对上面的结果，我们再引入一个变换：
则：
可以看到，上面这个结果，刚好就是公式(7)(8) 的结果，上面结果的向量中，元素1是公式(7)的结果，元素2是公式(8) 的结果。
这里，我们得到了一个新的方法：
先对
和
做 变换，分别得到一个向量，然后再对两个向量中对应元素相乘，得到一个向量，最后对这个向量做
的变换。
对公式 (5) 中，我们需要 考虑 ，我们把
的结果，记为
其中上标 p 表示 permutation（置换） 的意思，实际上就是 取了一个值
，通过乘以
， 就可以计算出一个
, 然后，公式（5） 中求和项的下标，就可以表示为：
则，公式(5) 可以写成：
我们暂时先忽略上标 p ，假如 公式 (5) 是如：
那么，我们可以用类似于二元 情况的，引入变换域算法。
我们来看一下公式 (5)，其中
有四种情况（以模 4 为例子）：
假如看 这个校验方程，则
, 那么
有四种取值，根据公式(5), 我们需要计算的概率有：
可以写成一个向量：
我们另外三个向量：
对上面三个向量分别做 变换,
由
计算得来：
则：
同理：
然后，把三个向量 做对应的元素相乘
再对上式的结果做 变换，其中：
那么：
就是公式(10) 的结果，也就是公式 (5) 的结果，因为 这个变换，是模 4 域里面的变换，可以用快速傅里叶变换的算法，降低运算量。
公式(11)(12)(13) 都是一种变换，从一个域变换到另外一个域，这里应该理解为在模 4 运算下的傅里叶变换，然后可以用快速傅里叶变换，快速傅里叶变换的算法如下：
对公式（11）
如果是 元的 LDPC 码，则这个变换就是
其中
则一个 s 维向量 , 则
按照如下公式计算：
我们举个例子来说明，假如我们要分析的是 8 元 LDPC 码，则每个数据有 3 个比特，我们把一个数据记为 c , 是由 3 个比特组成的数据，取值范围从 0 到 7. 这八种取值，都对应一个概率，8 个概率组成一个向量：
那么 的结果还是一个 8 维的向量，其结果为：
然后
最后
则 就是变换后的最终结果。
参考文献： 《多元 LDPC 码及其应用》 赵山程 马啸 白宝明著
