[数据结构与算法] NR Polar码二

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> NR Polar码二 -> 正文阅读

[数据结构与算法]NR Polar码二

前言：

? ? ? ? 回顾一下,前面讲的互信息I(X,Y) 本质上和机器学习中.决策树里面的ID3,C4.5

划分子树的思想是一样的,? 基于信息增益?

? ? ? ? ?通讯就像双方讲话,上一章通过理论上证明了跟对方讲话的最大速率（信道容量C）

这里通过编码方式（Polar码）提高通讯的稳定性。

跟讲话的方式很像:中文,普通话,英文等（编码）

参考文档：

? ? ? ? ??Polar码的原理

? ?1： Polar 主要思想

? ? 2??总体流程

? ?3：Basic transformation

? 4? ? Polar BEC 例子

一? ?Polar 主要思想

Polar 适用于二进制无记忆信道。

例如 BEC BSC。

传输N个bit, 通过极化后，

一类信道趋近于无噪声，用于传输信息

另一类为噪声信道, 用于传输冻结bit(frozen bits)

其中：

BEC 信道容量? $C=1-\epsilon$

BSC 信道容量? $C= 1-H(\epsilon )$

二总体流程

? ?? ?

? ? ? ?1? ? ? ? ? ?编码过程 combining

? ? ? ? ? ? ? ? ? ? ??生成新的信道：分为两类

? ? ? ? ? ? ? ? ? ? ? 噪声信道：? ? $Q^{-}$ :? $(Y_1,Y_2)\rightarrow u_1$ :? ,信道变得更差了

? ? ? ? ? ? ? ? ? ? ? 信息信道:? ? ? $Q^{+}:(Y_1,Y_2,u_1)\rightarrow u_2$ :信道变得更好了??

? ? ?

? ? ?2? ? ? ? ? ? ?解码过程 Spliting

? ? ? ? ? ? ? ? ? ??循序译码

? ? ? ? ? ? ? ? ? ? ?--- 根据 $(Y_1,Y_2)$ ?,译码出? $u_1$

? ? ? ? ? ? ? ? ? ? ?--- 根据 $(Y_1,Y_2,U_1)$ ?译码出 $u_2$ ,假设 $u_1$ 译码正确

? ? ? ? ? ? ? ? ?

三??Basic transformation

? ? ?

这是Polar 的核心思想，如何极化的

? ? ? 2.1? 基本结构（Basic transformation）

? ? ? ??

? ? ? ? ?? $X_1= u_1\bigoplus u_2$ ? (模2加,异或运算）

? ? ? ? ?? $X_2= u_2$ ? ? ? ?

? ? ? ? ?? $I(Q)=I(X_1,Y_1)=I(X_2,Y_2)=1-\epsilon$

? ? ? ? ? ?这里W都是BEC信道

? ? ? ? ? ? ? ? ? ? ? ?其中 $Q^{-}$ 信道：?

? ? ? ? ? ? ? ? ? ? ? ?? $u_1=\left\{\begin{matrix} Y_1 \bigoplus Y_2, Y_1,Y_2\in [0,1] \\ ? \bigoplus Y_2, Y_1=e,Y_2\in [0,1] \\Y_1 \bigoplus ?, Y_1\in [0,1] ,Y_2=e \\ ? \bigoplus ?, Y_1=e,Y_2=e \end{matrix}\right.$

? ? ? ? ? ? ? ? ? ? ? ?我们发现只有 $Y_1,Y_2$ 同时正确的时候， $u_1$ 才能正确解码

? ? ? ? ? ? 同时正确的概率为 $(1-\epsilon )^2$ ,则信道erasure probality为

? ? ? ? ? ? ? ? ? ? ? ? ? ? $\epsilon ^{-}=1-(1-\epsilon )^2$

? ? ? ? ? ?假设原始的BEC信道? $\epsilon =0.5$ ，极化后， $Q^{-}: \epsilon^{-}=1-0.5^2=0.75$

? 出错概率明显变高了

? ? $Q^{+}: u_2= \left\{\begin{matrix} Y_1 \bigoplus u_1, Y_1 \in [0,1] \\ Y_2 , if: Y_2 \in [0,1] \\ ?, if: Y_1=Y_2 =E \\ \end{matrix}\right.$

? ? ? ? ? ?这种场景:因为 $u_1$ 传输的一般都是冻结bit，如固定为0.

? ?只有 $Y_1,Y_2$ 同时出错的时候， $u_2$ 才会解码出错，erasure probality 为

? ? $\epsilon^{+}=\epsilon^2$

? ?假设原始的BEC信道? $\epsilon =0.5$ ，极化后， $Q^{+}: \epsilon ^{+}=0.25$

? 出错概率明显变低了

?通过上面发现一个 $Q^{-}$ 信道erasure probality 变大了， $Q^{+}$ ?信道 erasure probality 小了

?再看一下极化后的信道容量,能量不灭

?? $I(Q^{+})+I(Q^{-})$

? $=I(U_2;Y_1,Y_2,U_1)+I(U_1;Y_1,Y_2)$

$=2(1-\epsilon )=2I(Q)$

四 Polar BEC 例子

?3.1? 如下： N=4 ，需要做basic transformation 2次（ $log_2 N$ ）发送消息 $(u_1,u_2,u_3,u_4)$

? ?????????

3.2? erasure probality 更新过程

? 3.3? erasure probality 计算方法

? 其中

? ?? $Q^{-}$ : erasure probality?? $\epsilon^{-}=1-(1-\epsilon)^2=0.75$ ?

? ?? $Q^{+}$ : erasure probality? ? $\epsilon^{+}=\epsilon^2=0.25$

?第二步：

?多了一个sort 动作，把erasure probability?一样的，两两结合

再做一个 basic transformation

? 最终的目的是区分出好的信道，和烂的信道。?

3.4? 解码过程 splitting?

? ? ?从上面编码过程可以解码过程一个splitting 过程，依次解出U

? ? ? ? $U_1->U_2->U_3->U_4$

四? ?combing ?代码

? ? ? N = 8,用下面代码算结果是一样的：

? ? ? ? N= 1024 情况

# -*- coding: utf-8 -*-
"""
Created on Thu Apr  7 11:58:26 2022

@author: chengxf2
"""
import numpy as np
import matplotlib.pyplot as plt


def DrawErasure(erasureList,N):
    
    x = np.arange(0,N)
    
    y = erasureList
    fig = plt.figure()  
    ax1 = fig.add_subplot(111)  
    ax1.scatter(x,y,c = 'r',marker = 'o')  
    plt.ylabel("erasure")
    plt.xlabel("bit index")
    plt.legend('erasure')
    plt.show()

'''
basic transformation
BEC 信道
'''
def basic_transformation(e):
     good_channel = np.power(e,2)
     s = 1.0-e
     
     bad_channel = 1.0 - np.power(s,2)
     
     #print("\n good_probality %8.4f -----bad_probality %8.4f"%(good_channel,bad_channel))
     
     return [good_channel,bad_channel]

'''
polar 码
erasure probability 
'''
def Polar(N=4,erasureList=[0.5]):
    
    n = np.log2(N)
    if np.power(2,n) != N:
        print("\n error: ",n,N)
        
    n = int(n)
    for  i in range(n):
        
        print("\n ----迭代次数----- %d "%i)
        cur_erasure = []
        for e in erasureList:
            erasure = basic_transformation(e)
            cur_erasure.extend(erasure)
        
            
        cur_erasure.sort()
        #for erasure in cur_erasure:
            #print("\t errase: %8.4f"%erasure)
            
        erasureList =cur_erasure
    DrawErasure(erasureList,N)
        
        
#basic_transformation(0.5)
n= 11
N = np.power(2,n)
print("\n 输入bit 数",N)
Polar(N)

五 bit reverse

? ? ?

? ? ?主要作用是对输入进行重排。排序以后，使得在输入端

其中一半都是做的模二加法，另一半bit直接传过去。

1 N=8