基于Matlab的LDPC编解码算法实现及LDPC码性能测试

# LDPC 编解码仿真 ## 前言 ### 代码仓库引用 [](https://zenodo.org/doi/10.5281/zenodo.10939844) ### 文档乱码问题 **本文档使用Typora软件编辑，Github由于无法解析部分语法可能会出现乱码，出现乱码请使用Typora打开即可。** 行间公式出现乱码时：Typora软件勾选 “插入内联公式” 选项，点击“文件” --> “偏好设置” --> “Markdown” --> “Markdown扩展语法” —> 勾选 “内联公式（例：$ \LaTeX $）” 另外提供了无乱码的pdf版文档。 ### 仿真流程 仿真时无需输入额外参数，只需要把整个仓库clone到本地即可。 1. 首先运行SearchBestAlpha.m脚本得到误码率最低时的α取值； 2. 然后运行SearchBestBeta.m脚本得到误码率最低时的β值； 3. 把上面得到的α和β值在Comparasionof4Algorithms.m中确定下来，直接运行Comparasionof4Algorithms.m即可比较4种译码算法的误码率和误帧率曲线 ### 仿真时间 4种解码算法的比较脚本运行时间较长，只有当四个译码算法的误帧数都到达指定数量时才会停止运行  运行时长可能高达几个小时甚至几十个小时，运行后Matlab命令行窗口会每隔一定时间输出提示信息，建议可以晚上睡前运行脚本，睡醒可能就差不多跑完了。 如果想要早点结束可以设置Eb_N0_dB的值的范围到1或者1.5或更小的值。  ## 1. LDPC码背景及概要 LDPC是Low Density Parity Check Code英文缩写，意为低密度奇偶校验码，最早在20世纪60年代由Gallager在他的博士论文中提出，但限于当时的技术条件，缺乏可行的译码算法，此后的35年间基本上被人们忽略。直到1993年Berrou等人发现了Turbo码，在此基础上，1995年前后MacKay和Neal等人对LDPC码重新进行了研究，提出了可行的译码算法，从而进一步发现了LDPC码所具有的良好性能，迅速引起强烈反响和极大关注。经过十几年来的研究和发展，研究人员在各方面都取得了突破性的进展，LDPC码的相关技术也日趋成熟，逐渐有了商业化的应用成果，如今LDPC码已经作为众多新一代通信标准中的信道编码方案：DVB-S2 (Digital Video Broadcasting)、IEEE 802.3an (Ethernet)、IEEE 802.16e (WiMax)、IEEE 802.11n (WiFi)、3GPP 5G标准。 LDPC码是一种稀疏校验矩阵线性分组码，在LDPC编码中，会用到一个叫做H矩阵的校验矩阵(Parity Check Matrix)，该校验矩阵为稀疏矩阵。 LDPC编码分为正则编码和非正则编码。正则编码中，校验矩阵的每行和每列中1的个数是固定的。非正则编码中，校验矩阵的每行和每列中1的个数不固定。 LDPC解码过程中，主要包括了两方面内容：硬解码(Hard Decode)和软解码(Soft Decode). LDPC解码的方法就是收到码字之后，与校验矩阵H相乘，如果是0矩阵，则说明收到的是正确码字。反之，则不正确码字，再根据相乘结果进行进一步纠错解码 ## 2. 仿真要求及内容 本次仿真要求通过MATLAB软件对LDPC码进行编译码仿真，通过计算模拟求解归一化最小和算法α参数的最佳值和偏置最小和算法β参数的最佳值，并仿真出四种不同的译码算法下的误码率和误帧率曲线。实验的要求如下： 1. 采用系统码设计，信息序列长1008比特，码长2016比特，码率1/2，即 $$ N=2016,\ K=1008,\ R=1/2 $$ 2. 给定的编码矩阵 H_block 是一个18x36的矩阵（Matrix(2016,1008)Block56.mat文件中也是只有18x36个数据），矩阵中每个元素 H(i,j) 是大小为 z*z 的循环移位矩阵（给定z=56），行重为1，它的值表示该矩阵的循环位移偏移量，也是第一行中元素1所处的列的位置，若H(i,j)值为0，表示是全0矩阵。 3. 给定 $H\_block_{18×36}$ 矩阵，根据给定规则求解校验矩阵 $H_{1008, 2016}$ 。 4. 根据校验矩阵直接进行编码：利用输入信息比特序列$s$和校验矩阵$H$求得校验比特序列 $p$ ， $x = \lbrack p\ s\rbrack$ 即为编码序列。 5. 编码序列采用BPSK调制并通过AWGN信道添加噪声。 6. 完成以下四种译码算法的MATLAB代码实现 1. 和积算法（Sum-Product, SP） 2. 最小和算法（Min-Sum, MS） 3. 归一化最小和算法(Normalized Min-Sum, NMS) 4. 偏置最小和算法(Offset Min-Sum, OMS) 7. 对于归一化最小和算法和偏置最小和算法，选定一个Eb/N0（1dB附近），仿真BER得出α和β最佳值。α和β取值范围均为0到1，步进为0.1，α和β的BER曲线各画一张图。 8. 仿真得出Eb/N0在-1dB到2dB（步进0.5dB）时四种译码算法的BER和FER，两个修正最小和算法的α和β都取最佳值。应画BER一张图，FER一张图，每一张图都包含四种算法。 ### 2.1. LDPC编码算法 LDPC码通常由校验矩阵H进行定义。尽管线性分组码可以使用传统的生成矩阵进行编码，但是要通过H求解G在实现上较为困难，因此根据校验矩阵直接进行编码。本次作业采用系统码，且校验矩阵H可分为两部分$$ H=\left[ H_p|H_s \right] $$，其中$$ H_p $$对应校验比特部分，对$$ H_s $$应信息比特部分；编码序列x可分为$$ x=\left[ p\ s \right] $$，其中$p$为校验比特序列，$s$为信息比特序列。本作业的编码部分有两种编码算法用以实现LDPC编码。 #### 2.1.1. LDPC编码算法1 由于校验矩阵H的性质： $$ Hx^T=0 $$ 因此可采用基于H矩阵的通用LDPC编码方法： $$ Hx^T=0\Rightarrow \left[ H_p,H_s \right] \left[ \begin{array}{c} p^T\\ s^T\\ \end{array} \right] =0\Rightarrow p=sH_{s}^{T}\left( H_{p}^{T} \right) ^{-1} $$ 由上式可知，本算法需要$H_{p}$可逆，且上式p为1x(N-K)向量、s为1xK向量、$H_{s}^{T}$为Kx(N-K)矩阵、$H_{p}^{T}$为Kx(N-K)矩阵，因此该算法需要$K(N - K) + (N - K)(N - K)$次比特乘法运算和$(K - 1)(N - K) + (N - K - 1)(N - K)$次比特加法运算。 #### 2.1.2. LDPC编码算法2 将基于H矩阵的通用LDPC编码方法进行分解，具体步骤如下： 1) 首先利用信息序列s计算中间结果 $$ w=sH_{s}^{T}\quad w=\left[ w_1,w_2,\cdots ,w_{m_bz} \right] $$ 2) 利用编码序列x计算校验比特 $$ Hx^T=0\Rightarrow \left[ H_p,H_s \right] \left[ \begin{array}{c} p^T\\ s^T\\ \end{array} \right] =0\Rightarrow pH_{p}^{T}=sH_{s}^{T} $$ 故可得： $$ p_i=\left\{ \begin{matrix} w_i& i=1& \\ w_i\oplus p_{\left( m_b-1 \right) z+i-1}& 1<i\leq z& p=\left[ p_1,p_2,\cdots ,p_{m_bz} \right]\\ w_i\oplus p_{i-z}& i>z& \\ \end{matrix} \right. $$ 此算法易错处为： 上式中运算过程是应由右侧值决定左侧值，即只有当右侧表达式中各变量的值被赋过一次值时才能对左侧值赋值。例如： - 当i=1时，w1已知，p1=w1 - 当i=2时，w2已知，但p(mb-1)\*z并没有值，因此此时还不能立刻求p2，而是应该求p(z+1)=w(z+1) 模二求和 p(1)。即： -当i=(z+1)时，w(z+1)已知，p(1)已知，p(z+1)=w(z+1) 模二求和 p(1) - ... 3) 组合p与s $$ x=\left[ p\ s \right] $$ 将校验比特序列p和信息比特序列s组合即得到编码序列x。 4) 检验 由于编码过程利用的是 $$ Hx^T=0 $$ 因此，得到编码序列x后需要对x进行检验，保证其满足上式即表明完成了正确编码工作。 #### 2.1.3. 两种算法比较 两种算法在时间复杂度上的区别如图所示（$\left( H_{p}^{T} \right)^{- 1}$可以离线求解，所以不占用复杂度）， 两种编码算法的时间复杂度对比 ![alt]