线性编码技术

2024-05-25

线性编码技术（精选七篇）

线性编码技术篇1

循环冗余码CRC技术是一种典型的线性编码与差错控制技术, 广泛应用于计算机、工业控制、自动化测控及通信领域。CRC计算可以靠专用的硬件来实现, 但是对于低成本的微控制器系统, 在没有硬件支持下实现CRC检验, 关键的问题就是如何通过软件来完成CRC计算, 也就是CRC算法的问题。在现有的非线性编码CRC算法中, 一种适用于程序空间十分苛刻但CRC计算速度要求不高的微控制器系统, 另一种适用于程序空间较大且CRC计算速度要求较高的计算机或微控制器系统。本文提出一种在校验与检测过程中基于CRC码C语言实现技术, 且适用于程序空间不太大与CRC计算速度快的微控制器系统的线性编码与差错控制方法。目的是提高在S3C2410AL-20微处理器系统中进行二次开发的效率, 解决在选择微处理器时容量与速度之间的矛盾。

在软件编程实现方面, 阳璞琼等利用递归公式法设计了一种算法简单、结构紧凑、运算速度快的并行CRC电路, 并在超高频射频身份识别 (RFID) 系统中实现, 可减低标签碰撞频率, 其缺点在于一旦识别精度要求高、程序量大时将会使系统性能大大降低[1]。常晓明等提出了一种用8031汇编语言实现CRC校验的程序设计方法, 并将该技术应用在测控系统中[2]。朱荣华提出一种通用的CRC并行计算原理及实现方法, 该方法在减少时延、降低高速数传系统的CRC运算的时钟频率方面发挥重要作用[3]。解小东等给出了一种在数字通信中适用于通用成帧协议的快速CRC算法[4], 以VHDL源程序实现, 在提高效率、降低硬件资源消耗方面起到积极的作用, 但对通用高级语言的适应性较差。

1 CRC编码与实现

1.1 CRC校验与算法原理

该原理的基本思想是基于线性编码理论, 发送端需传送的k位二进制码序列, 以一定的规则产生一个校验用的监督码 (即CRC码) r位, 并附在信息后边, 构成一个新的二进制码序列数共 (k+r) 位, 最后发送出去。接收端则根据信息码和CRC码之间的规则进行检验, 以确定传送数据是否出错。

如在16位的CRC码中, 则是先将要发送的二进制序列数左移16位 (即乘以216) 后, 再除以一个多项式, 最后所得到的余数既是CRC码, 如式 (1) 所示:

$\frac{B (X) \cdot 2^{16}}{G (X)} = Q (X) + \frac{R (X)}{G (X)} (1)$

式中:B (X) 表示n位的二进制序列数;G (X) 为多项式;Q (X) 为整数;R (X) 是余数 (即CRC码) 。求CRC码所采用模2法则, 实际上就是逻辑上的异或运算, 加法和减法等价, 乘法和除法运算与普通代数式的乘除法运算是一样, 符合同样的规律。生成CRC码的多项式, 其中CRC-16和CRC-CCITT产生16位的CRC码, 而CRC-32则产生的是32位的CRC码。

CRC-16 (在美国二进制同步系统中采用) :

$G (X) = X^{16} + X^{15} + X^{2} + 1 (2)$

CRC-CCITT (由欧洲CCITT推荐) :

$G (X) = X^{16} + X^{12} + X^{5} + 1 (3)$

CRC-32:

$\begin{array}{l} G (X) = X^{32} + X^{26} + X^{23} + X^{22} + X^{16} + X^{12} + \\ X^{11} + X^{10} + X^{8} + X^{7} + X^{5} + X^{4} + \\ X^{2} + X^{1} + 1 (4) \end{array}$

在接收方将接收到的二进制序列数 (包括信息码和CRC码) 除以多项式, 如果余数为0, 则说明传输中无错误发生, 否则说明传输有误。用软件实现CRC码时, 接收方可以将接收到的信息码求CRC码, 比较结果和接收到的CRC码是否相同, 确定其有效性。

1.2 CRC编码的高级语言实现

1.2.1 C语言实现按位计算CRC

根据二进制编码理论, 对于一个二进制序列数按字节表示为式 (5) :

$\begin{array}{l} B (X) = B_{n} (X) \cdot 2^{8 n} + B_{n - 1} (X) \cdot 2^{8 (n - 1)} + \dots + \\ B_{1} (X) \cdot 2^{8} + B_{0} (X) (5) \end{array}$

式中:Bn (X) 为一个字节 (共8位) 。求此二进制序列数的CRC码时, 先乘以216后 (即左移16位) , 再除以多项式G (X) , 所得的余数即是所要求的CRC码, 如式 (6) 所示:

$\begin{array}{l} \frac{B (X) \cdot 2^{16}}{G (X)} = \frac{B_{n} \cdot 2^{16}}{G (X)} \cdot 2^{n} + \frac{B_{n - 1} \cdot 2^{16}}{G (X)} \cdot 2^{n - 1} + \dots + \\ \frac{B_{1} \cdot 2^{16}}{G (X)} \cdot 2 + \frac{B_{0} \cdot 2^{16}}{G (X)} (6) \end{array}$

设:

$\frac{B_{n} \cdot 2^{16}}{G (X)} = Q_{n} (X) + \frac{R_{n} (X)}{G (X)} (7)$

式中:Qn (X) 为整数;Rn (X) 为16位二进制余数。将式 (7) 代入式 (6) 可变换得到:

$\frac{R_{n} (X) \cdot 2}{G (X)} + \frac{B_{n - 1} \cdot 2^{16}}{G (X)} = Q_{n - 1} (X) + \frac{R_{n - 1} (X)}{G (X)} (8)$

式中:Qn-1 (X) 为整数;Rn-1 (X) 为16位二进制余数, 将式 (7) 代入式 (6) , 依次类推, 最后得到:

$\begin{array}{l} \frac{B (X) \cdot 2^{16}}{G (X)} = Q_{n} (X) \cdot 2^{n} + Q_{n - 1} (X) \cdot 2^{n - 1} + \\ Q_{n - 2} (X) \cdot 2^{n - 2} + \dots + Q_{0} (X) \cdot 2^{0} + \frac{R_{0} (X)}{G (X)} (9) \end{array}$

可以看出, 16位二进制数R0 (X) 即是CRC码。式 (8) 是编程计算CRC的关键, 说明计算本位后的CRC码等于上一位CRC码乘以2后除以多项式, 所得的余数再加上本位值除以多项式所得的余数。不难理解下面求CRC码的C语言程序, *ptr 指向发送缓冲区的首字节, len是要发送的总字节数, 0x1021与多项式有关。

按位计算CRC虽然代码简单, 所占用的内存比较少, 但其最大的缺点就是逐位计算会占用很多的处理器处理时间, 尤其在高速通信的场合, 这个缺点更是不可容忍。

1.2.2 C语言实现按字节计算CRC

同样, 对于一个二进制序列数可以按字节表示, 在求二进制序列数的CRC码时, 先乘以216后 (即左移16位) , 再除以多项式G (X) , 所得的余数即是所要求的CRC码, 如式 (10) 所示:

$\begin{array}{l} \frac{B (X) \cdot 2^{16}}{G (X)} = \frac{B_{n} (X) \cdot 2^{16}}{G (X)} \cdot 2^{8 n} + \\ \frac{B_{n - 1} (X) \cdot 2^{16}}{G (X)} \cdot 2^{8 (n - 1)} + \cdot \cdot \cdot + \frac{B_{0} (X) \cdot 2^{16}}{G (X)} (10) \end{array}$

又设:

$\frac{B_{n} (X) \cdot 2^{16}}{G (X)} = Q_{n} (X) + \frac{R_{n} (X)}{G (X)} (11)$

式中:Qn (X) 为整数, Rn (X) 为16位二进制余数。将式 (11) 代入式 (10) 进行变换, 设RnH8 (X) 是Rn (X) 的高8位, RnL8 (X) 是Rn (X) 的低8位, 最后得到式 (12) 。

$\begin{array}{l} \frac{R_{n L 8} (X) \cdot 2^{8}}{G (X)} + \frac{[B_{n Η 8} (X) + B_{n - 1} (X)] \cdot 2^{16}}{G (X)} = \\ Q_{n - 1} (X) + \frac{R_{n - 1} (X)}{G (X)} (12) \end{array}$

式中:Qn-1 (X) 为整数;Rn-1 (X) 为16位二进制余数。再如上类推, 最后得:

$\begin{array}{l} \frac{B (X) \cdot 2^{16}}{G (X)} = Q_{n} (X) \cdot 2^{8 n} + Q_{n - 1} (X) \cdot 2^{8 (n - 1)} + \dots + \\ Q_{0} (X) + \frac{R_{0} (X)}{G (X)} (13) \end{array}$

显然, 16位二进制数R0 (X) 即是CRC码。式 (12) 是编写按字节计算CRC程序的关键, 如果把8位二进制序列数的CRC全部计算出来, 放在一个表里采用查表法, 可以大大提高运算速度。下面的程序中, *ptr 指向发送缓冲区的首字节, len是要发送的总字节数, CRC余式表是按0x11021多项式求出的。

在按字节求CRC时, 由于采用了查表法, 大大提高了计算速度。但对于广泛运用的8位微处理器, 代码空间有限, 对于要求256个CRC余式表 (共512字节的内存) 已经显得捉襟见肘了, 但CRC的计算速度又不可以太慢, 因此, 可以按半字节求CRC的算法解决这个问题。

1.2.3 C语言实现按半字计算CRC

依据同样步骤, 对于一个二进制序列数可以按字节表示为式 (14) , 如:

$\begin{array}{l} B (X) = B_{n} (X) \cdot 2^{4 n} + B_{n - 1} (X) \cdot 2^{4 (n - 1)} + \dots + \\ B_{1} (X) \cdot 2^{4} + B_{0} (X) (14) \end{array}$

式中:Bn (X) 为半个字节 (共4位) 。在求二进制序列数的CRC码时, 先乘以216后 (即左移16位) , 再除以多项式G (X) , 所得的余数即是所要求的CRC码。如上, 可按字节计算CRC的原理, 最后得到式 (15) 和式 (16) 。

$\begin{array}{l} \frac{R_{n L 12} (X) \cdot 2^{4}}{G (X)} + \frac{[B_{n Η 4} (X) + B_{n - 1} (X)] \cdot 2^{16}}{G (X)} = \\ Q_{n - 1} (X) + \frac{R_{n - 1} (X)}{G (X)} (15) \end{array}$

式中:Qn-1 (X) 为整数;Rn-1 (X) 为16位二进制余数;RnL12 (X) 是Rn (X) 的低12位;RnH4 (X) 是Rn (X) 的高4位。

$\begin{array}{l} \frac{B (X) \cdot 2^{16}}{G (X)} = Q_{n} (X) \cdot 2^{4 n} + Q_{n - 1} (X) \cdot 2^{4 (n - 1)} + \dots + \\ Q_{0} (X) + \frac{R_{0} (X)}{G (X)} (16) \end{array}$

从公式可以得到, 16位二进制数R0 (X) 即是所求的CRC码。式 (15) 是编写按半字节计算CRC程序的关键, 它说明计算本字节后的CRC码等于上一字节CRC码的低12位左移4位后, 再加上上一字节余式CRC右移4位 (也即取高4位) 和本字节之和后所求得的CRC码。如果把4位二进制序列数的CRC全部计算出来, 放在一个表里, 采用查表法, 每个字节算两次 (半字节算一次) , 可以在速度和内存空间取得均衡。由此, 不难理解下面按半字节求CRC码的C语言程序, *ptr指向发送缓冲区的首字节, len是要发送的总字节数, CRC余式表是按0x11021多项式求出的。

2 实验与结论

系统开发板的核心使用三星公司S3C2410AL-20微处理器, 它是一款基于ARM920T内核的RISC型CPU, 核心板提供64 MB的NANDFLASH及64 MB的SDRAM, 具有3个独立的异步串口。程序在PC机上编写、仿真并运行。与Ldpc码的生成矩阵和校验矩阵比较[7], 其稀疏矩阵更接近和Shannon极限, 运算速度更快, 适合嵌入式系统、移动通信中的突发信道与分析学领域。在与低密度校验码校验编码比较[8,9,10], 按半字计算的CRC结构更接近容量的LDPC码, 可以降低计算成本, 提高内存使用率。首先将数据放入RAM, 把每一个存储单元的数据看成是同步传输数字序列的个位来进行处理的, 得到的实验结果如表1所示。

上面介绍的3种CRC算法的C语言实现方法, 测试中按位求法速度较慢, 但占用最小的内存空间;按字节查表求CRC的方法速度较快, 但占用较大的内存;按半字节查表求CRC的方法是前两者的均衡, 即不会占用太多的内存, 同时速度又不至于太慢, 比较适合8位小内存的单片机的应用场合, 可以获得均衡的运算结果, 即平衡微处理器速度和存储器之间的矛盾。

3 结语

本文通过C语言实现CRC算法在微处理器上进行信息传输, 相比利用哈夫曼编码进行设计的C程序, 具有几点优势:

(1) 在数据传输时可以大大提高信道利用率, 缩短信息传输时间;

(2) 按位、按字节和按半字计算时, 误检率随编码位数增加显著减低, 降低信息传输成本;

(3) 实验证明, 基于芯片S3C2410AL-20微处理器选用C语言实现CRC编码算法可以在编码效率和内存占有率上获得较好的效果, 与利用哈夫曼编码传输相比, 译码时间更短。

当数据运算量增大时, 但又要求在发送端通过编码系统对待传数据预先编码, 或在接收端将传来的数据进行译码 (复原) , 要想获得更好的传输效果, 仍需进一步研究在选择微处理器处理数据时存储容量与速度之间的矛盾, 特别是相邻数据之间差异性, 以提高C语言实现编码的效率。

参考文献

[1]阳璞琼, 何怡刚, 谭阳红, 等.超高频RFID系统CRC电路设计[J].电路与系统学报, 2009 (2) :18-21.

[2]常晓明, 潘卫华, 王建东.CRC校验及其软件实现[J].电子技术应用, 1995 (6) :14-16.

[3]朱荣华.一种CRC并行计算原理及实现方法[J].电子学报, 1999 (4) :113-115.

[4]林桦, 王伟.CRC算法原理及其在MPEG-2系统层中的应用[J].计算机工程与应用, 2004 (8) :110-113.

[5]谢小东, 周正欧.GFP中一种快速CRC算法及其实现[J].电讯技术, 2005 (4) :165-168.

[6]张文静, 慕德俊, 刘航, 等.基于硬盘加密卡的CRC并行算法及其仿真[J].计算机仿真, 2008 (8) :123-126.

[7]张志亮, 卿粼波, 刘英.一种线性编码半随机构造LDPC码及其仿真[J].通信技术, 2009 (2) :12-14.

[8]李会雅, 王兰勋, 师建英.低密度校验码的蚕食算法线性编码[J].现代电子技术, 2005, 28 (11) :79-81.

[9]王学东, 孙坚.低密度校验码的编码结构[J].通信技术, 2003 (9) :36-37, 40.

线性编码技术篇2

关键词：图像分类,局部约束线性编码,向量量化

近年来词袋模型BOW[1—3]在图像分类领域中获得了广泛应用;该模型把一幅图像当成一些从图像中提取的若干无序的局部特征, 然后对这些特征进行聚类 (通常为k-means) 形成视觉字典;最后统计出整幅图像中所有视觉词汇的出现频率直方图来表示图像。由于词袋模型对平移、旋转等几何变换鲁棒性较强, 视觉词袋模型在场景分类、物体识别等具体图像分类任务中取得了巨大成功, 受到学术界和工业界的广泛关注。但是传统BOW的方法并未考虑到图像中局部特征之间的位置关系, 这一点制约了他的描述能力。针对这个问题, Lazebink等人[4]提出了SPM;这种方法取得了比传统BOW的方法更好的分类效果。除了缺乏对空间信息的刻画外, 在传统BOW模型中, 其中的字典学习和特征编码两个关键环节也存在一些不足。在聚类学习字典的时时候, 首先要面临的问题是如何确定一个合适的字典大小, 过大或过小都会影响字典的描述能力。

1 基于BOW的SPM图像分类模型

在典型的基于BOW的SPM方法中, 首先提取输入的图像的局部特征, 形成特征描述符。然后对这些特征描述符进行量化编码, 如图1所示。

在编码过程中, 如果采用硬关联编码 (hard assignment coding, HAC) 的方法, 最后输出的编码只有一个非零元素;如果采用软关联编码[5] (soft assignment coding, SAC) 的方法, 最后输出的编码会有多个非零元素。接下来, 在SPM层, 通过来自不同尺度的对各尺度上的特征分别汇总, 最后将不同尺度上汇总的特征串接起来, 形成最终描述图像的全局向量[4,5]。

字典学习和向量量化是BOW模型中的两个关键步骤, 它们直接决定了BOW模型最后的性能。字典学习是为了寻找一种具有较强表达能力的特征空间, 而向量量化则是为了寻找一种局部特征编码方法, 以实现从原始特征空间到新特征空间的映射。近年来的研究结果表明, 当字典大小达到一定规模之后, 不同的字典学习方法对最终的结果的影响非常有限。在图像检索应用中, 字典规模一般都会比较大, 往往在几十万、数百万数量级以上, 此时就算是采用简单随机采样也可以得到一个分类性能比较好的字典。相反, 不同的特征量化方法则会对最终分类结果产生显著的影响[6—10]。提出了一种新的方法来解决图像分类中量化编码的问题, 并在两个常用的标准数据集Caltech-101, Caltech-256上作了验证。

2 局部约束线性编码及改进算法

2.1 局部约束线性编码

在相关变量中, 用bi (bi∈Rd) 来表示一个虚拟词汇或者一个基向量, d表示局部特征的维数。虚拟词汇总的个数是n, 矩阵Bd×n= (b1, b2, …, bn) 表示一个虚拟码本或者基向量的集合。xi (xi∈Rd) 表示第i个局部特征。最后用ui (ui∈Rd) 表示特征xi的编码系数向量, uij表示单词bj的系数。

在量化编码过程中, 早期词袋模型主要采取HAC的方法, 利用最近邻算法选择词典中与待编码局部特征距离最近的视觉词汇来表示局部特征。在这种策略下, 每个局部特征只能与1个视觉词汇相关联, 造成了很大的信息损失, 难以处理处于不同词汇中间区域 (类边缘地带) 的局部特征。公式如下:

uij={01, , j其=他argminj=1, …, n||xi-bj||22 (1)

J.Yang等人[11]提出一种与软关联编码相类似的策略稀疏编码 (sparse coding, SC) , 也是允许每个局部特征用多个视觉词汇来表示, 有效降低了量化误差, 提高了局部特征编码性能。不同之处在于稀疏编码的策略是使重建量化误差最小, 同时保证编码的稀疏性, 通过解决1范数约束的问题来计算输出的系数u。

λ是用来控制输出编码的稀疏程度的参数。

正如LCC[12]所指出的局部性比稀疏性更加重要。因为局部性必然保证编码结果具有稀疏性, 但稀疏性不一定能确保局部性。所以LLC采用局部性的约束方程而不是稀疏性的。

s.t.lTui=l这里di=exp (dist (xi, B) /σ) , dist (xi, B) =[dist (x1, B) , dist (x2, B) , …, dist (xi, B) ]T表示特征xi与每个虚拟词汇B之间的欧式距离。

2.2 改进算法

在编码过程中, 由于式 (3) 的计算复杂度比较高, 所以采用了近似LLC编码方式, 它是LLC编码的快速近似编码。它用KNN规则寻找与局部特征xi最近邻的K个基向量Bi, 通常K<0.1×M, M是码本的基的个数, 在这里选取K=5。以这5个基向量作为局部坐标系进行局部线性编码, 则其编码见式 (4) 。将生成的编码C采用max-pooling[13—15]的联合规则进行特征联合, 即选取C每一列的最大值, 采用空间金字塔匹配联合后的特征, 形成图像特征向量。

式 (4) 中Bi={bi1, bi2, …, bij}是xi的局部坐标基, 表示局部特征点xi相对于近邻点Bi的局部编码。以上三种编码方法的比较, 如图2所示。

在VQ过程中, HAC的每个描述符是由码本中一个虚拟词汇来表示, 如图2 (a) 所示。由于量化误差比较大, 对于相似的描述符的VQ后的编码可能完全不同, 另外VQ过程忽略了不同的词汇之间的关系。在SC中, 如图2 (b) 所示, 由于码本的过完备性, 对于相似的特征描述符选择完全不同的虚拟词汇来表示, 因此也失去了词汇之间关系。在LLC中, 每个描述符是由码本中多个虚拟词汇更加精确的表示, 如图2 (c) 所示, 在两个相似描述符中有相同的虚拟词汇, 这是因为LLC中的局部约束子确保了相似的特征描述符能有相似的编码[16]。

3 实验结果与分析

在Caltech-101, Caltech-256标准数据集上的实验结果, SIFT描述子采用密集采样的方式, 即以光栅扫描顺序, 从每幅图像中以步长8像素等间隔的提取若干16×16的图像块。选用128维的SIFT描述符来描述每个局部图像块, 实验中先将所有彩色图像转化为灰度图像, 所以并未利用彩色信息。

3.1 Caltech-101

Caltech-101数据集包含了9144张图片101个类别, 其中包括动物, 汽车, 花等, 在外形上都有显著的区别。每一类的图片数量从31到800不等。把每一类的训练图片把分成5, 10, …, 30不等, 测试图片每一类不超过50。训练的字典大小为2048, 使用了4×4, 2×2和1×1子区域来SPM。在实验中, 将图像的大小调整为不大于300×300像素, 保留它的宽高比。当每一类训练图片数为30时, 总共有13类, 包括accordion, car, leopards, rooster, chair等, 达到了100%的分类准确率。结果和现有的方法进行了比较, 结果如表1中所示。

可以看到大多数情况下, 提出的LLC方法的效果更好。另外, LLC处理一张图片形成最后的表示只需要0.24 s。

3.2 Caltech-256

Caltech-256数据集包含了30 607图片256个类别。它在物体的大小, 位置, 姿势等方面区分性更强。每个类别至少包含80张图片。将图像的大小调整为不大于300×300像素, 保留它的宽高比。实验中, 采用了常规的设置, 每一类中的训练图片有15, 30, 45和60不等, 训练的字典大小为4 096, 使用了4×4, 2×2和1×1子区域来SPM。如表2中所示。

LLC方法要比现有的其他方法的分类准确率要高6%左右, 另外处理每张图片的时间也只需要0.3秒。当每一类的训练图片为60时, 有20类最容易区分出来, 其中包括bonsai, chandelier, globe, eiffeltower和fireworks等。

4 总结

线性编码技术篇3

关键词：分布式文件存储,对等网络,线性编码,多播,随机线性网络编码

0 引言

伴随着两千年以来网络技术的迅猛发展, 信息化在现代工业的各个领域的普及, 对大量的数据存储需求越来越大。传统的基于单机的文件系统受限于存储容量小, 共享方式单一且效率低下等不利因素, 已经不能满足办公自动化或工业生产信息化领域中对大量数据存储和高效共享的要求。这就催生了存储容量更大, 数据共享更加灵活且高效的分布式文件系统的发展。

分布式文件系统 (Distributed File System, DFS) 是一种有效的存储管理策略, 通过它管理员能够方便有效地集中分散的资源, 同时使用者可以直接在视图上建立目录和文件的创建, 并不用考虑这些目录和文件的存放位置。不同于如Global File System (GFS) 、NFS、AFS、Coda等应用于局域网分布式文件系统, P2P构建的分布式文件存储系统一般都是面向广域网提供大规模网络存储服务, 利用其分布在广域网上的大量的服务器为用户提供安全的、可靠的和高效的存储访问服务, 但同时随着BT (Bit Torrent) 等P2P应用的广泛出现, P2P占用网络资源大的劣势也凸现出来。据估计, 截至目前为止, P2P应用占据了互联网上7O%以上的网络流量[1]。伴随着人们永无休止的追求数据的存储容量和共享速率, 基于传统路由转发的分布式文件系统颓势已现。

在现代计算机网络技术中, 网络的中间节点 (路由器) 一般只执行存储并转发的信息处理。通信方式一般采用单播 (输入的信息流被直接转发给下一个节点) 或者组播 (被复制之后转发给多个节点) 方式。这样的路由机制认为网络中传输的信息是不能叠加的。然而, 网络编码的提出推翻了这一结论, R.Alshwede等在200O年的IEEE信息论会刊上发表的一篇著名论文[2]提出了网络编码的概念并证明:如果允许网络节点对传输的信息按照合适的方式进行编码处理 (如模二加、有限域上的运算等) , 而非限于存储和转发, 则基于该方式的网络多播总能够实现理论上的最大传输容量.网络节点对传输信息进行操作和处理的过程, 就称为网络编码。

1 网络编码原理

1.1 网络编码的原理及分类

LW.Yeung和N.Cai在2000年首次提出了网络编码的概念, 其核心思想就是网络中的节点对输入的多路信息进行代数组合运算, 从而形成一路或者多路的新的信息, 而不是传统路由的简单的存储与转发的信息处理方式。

如果中间节点对接收的信息进行线性操作, 则称为线性网络编码 (Linear Network Coding:LNC) ;否则称为非线性网络编码。如果网络节点对信息进行操作的系数是随机选取的, 则称为随机网络编码;如果是通过算法确定出来的, 则称为确定性网络编码。

1.2 线性网络编码

定义: (性编码多播) , 所谓线性编码多播 (Linear Code Multicast, 简称LCM) , 就是给无环有向网络G= (V, E) 中每个节点X∈V定义一个向量空间v (X) 给每条链路e (X, Y) ∈E赋予一个编码向量x (X, Y) , 使得:

(1) v (S) ∈Ω, Ω为信源发出的足够大的域Fq上h维符号向量空间;

(2) 对于每链路XY, 均有v (XY) ∈V (X) ;

(3) 对于任何非源节点集合=Φ=V/{S}:<{v (T) |∈Φ}>=<{v (XY) |X∈Φ, Y∈Φ}>, 其中<●>表示向量张成的空间。

LCM提供了以信息民流描述网络中信息传输和编码操作的统一方式。

对于信宿节点tj的h条输入链路, 传输的信息流向量为:

1.3 随机线性编码

虽然由P.Sander等人提出的能够保证编码数据完全无误译码的集中式算法:多项式时问算法[3]可以有效的构造编码向量, 但由于其集中的编码方式, 必须明确网络拓扑结构并且要求维护一个相对稳定的网络拓扑, 所以线性网络编码方式的意义大多停留在理论研究的层面上。M.Medard在2003年提出的在有限域上的随机线性编码实现了一种更为实用的分布式网络编码方法: (Random Network Coding:RNC) 。基于有限域的特点:

(1) 有限域上仅包含有限个元素;

(2) 有限域上的加, 乘运算是封闭的。

RNC采用对于除信宿节点的中间节点随机且独立的对于该节点的输入链路和输出链路选取有限域Fq上的映射, 只要保证Fq足够大, 就能使得系统转移矩阵较高概率满秩, 使得信宿节点能以较高概率成功译码。

如图1, 随机线性编码中, 数据链路上随机网络编码的编码映射向量和信源发送的数据流, 编码映射向量ξ1, ξ2, ξ3……ξn在映射有限域Fq上随机选取, 在经过中间节点时, 根据中间节点随机选取的编码映射, 对接受链路上的影射进行重新映射。

定理 (RNC译码成功率) 对于信源相互独立或线性相关的LCM, 所有节点的全局编码向量都在有限域Fq上独立均匀选取 (某些节点的编码向量可固定, 只要这些固定向量对整个系统的网络编码是可行的) , 则接收节点能以最小概率 (1-d/q) η译出信源发送的信息, 其中q>d为编码符号域的大小, d是信宿节点的数目, η是随机选取编码系数的链路的数目。

根据RNC译码成功率定理, 我们可以看出当编码符号有限域Q足够大时, 信宿节点总能以较大概率译码原信息。根据定理, 当q=216时, 所有多播网络中的节点译码成功率可达99.6%[4]。曾有人证明在实际应用场合中, 编码符号有限域q=28时, 就能够满足应用需求了[5]。

2 分布式文件存储系统

2.1 P2P分布式文件存储系统

在P2P环境下的分布式文件存储系统中, 文件数据被分布在广域网中的离散的并且相互独立且平等的服务器集群中, 每一个服务器称为一个节点服务器。这些服务器根据一定的路由机制组成一个虚拟的P2P网络。此网络中的每台服务器具有相同的功能, 并且地位平等。此网络中的任意两台服务器均能相互通信。用户的存储访问服务由这个P2P网共同承担。

通过P2P路由机制将P2P文件存储系统中的服务器链接成为一个虚拟的P2P网络, 其物理层的拓扑结构可能不同。在这个虚拟的网络中, 每一个节点服务器都被编以一个全局SID来加以标识。同时, 每个节点服务器都各自维护一个保存自己邻居节点的路由表。这样, 任意服务器上的文件都可以方便的路由到其他节点服务器上。整个P2P文件存储系统上的每一个文件对象也都编以一个文件全局标识FID, 并且这个FID都对应一个SID作为其根节点。通过这个对应关系, 根据FID来对目标文件进行定位。

P2P没有中央控制机构, 能够有效避免传统分布式文件系统中央控制瓶颈的问题, 具有良好的可扩展性、自组织性和容错性。但是, 目前互联网上流行的P2P协议, 如BT (bit torrent) 采取不编码方式, 这样, 网络中的下载用户必须接收到目标文件的所有部分, 才能够完成的还原出原文件。这样的方式不利于节约网络带宽, 不能有效平衡系统负载并且会造成网络拥塞。

2.2 基于随机线性网络编码的分布式文件系统

网络编码是一种完全分布式在数据处理方式。数据编码能够在信源节点和中间节点同时进行, 信源服务器对目标文件进行分割, 然后进行编码, 编码方式采用有限域上的随机线性网络编码。

编码:可以设目标文件被分割成为个数据块, M1, M2, M3......Mn并由信源节点发出。直接与信源节点邻接的中间节点接收这n个数据块, 然后选取有限域Fq上的随机编码向量对其进行编码, 然后生成新的编码数据块, 并将这个新的数据块和编码向量同步发送。定义这种编码发送方式下发送数据为一个序偶。由于运算在有限域上进行, 数据块Xj占用内存与占用的内存完全相同。

译码:当一个节点接收到个编码数据包后, 译码然后产生信源接点发出的n个目标文件原始数据包M1, M2, M3......Mn的过程就是求解下列方程组 (4) 的过程。

由线性方程组求解条件可知, 要求解这个有n个未知数和m个方程的线性方程组, 并且要求方程有唯一解的必要条件是m≥n由于不同的编码数据包中的编码向量可能会出现线性相关, 所以m≥n并不是方程组有解的充分条件。然而, 当产生编码向量的有限域有一定的容量时, 这种编码向量间线性相关的可能性将非常小。同时, 经过实验证明[6], 即使所选取的有限域容量比较小时, 编码向量间的线性相关性也是非常小的。

节点的译码过程是相对简便的, 译码过程的计算也相对单一。不同于Bit Torrent必须接受到信源发出的所有指定内容数据包才能还原目标文件, 基于随机线性网络编码的分布式文件存储系统中节点能够准确还原目标文件只需要接受到足够数量的线性无关的数据包。

2.3 性能分析

传统的基于存储转发的路由机制, 接收到两个不同数据包存储并转发的过程需要将这两个数据包排队并发送, 需要两个单位的处理时间。当在单信源多信宿组播的环境中, 信源在与不同信宿的最大流路径中可能形成共享链路, 存储转发路由机制会使得共享链路上的数据传输效率低下。而采用线性网络编码的方法在单信源多信宿的环境下一定可以达到“最大流, 最小割 (MAX—FLOW MIN—CUT) ”定理确定的最大理论传输容量[7]。同时, 网络编码多播可有效利用除多播树路径外其它的网络链路, 可将网络流量分布在更广阔的网络空间上, 有效利用网络带宽, 进而均衡网络负载。

在一个大范围分布式的P2P系统中, 找到最优的分组发送时间十分复杂, 尤其是主机对于底层网络拓扑知之甚少的情况下更是如此, 而使用网络编码, 网络拓扑和发送先后对文件发送时间的影响将会大大减小。并且, 由于编码后的分组具有多样性的特点, 即使服务器在文件下载过程中离线, 或某些网络节点下载结束后立刻离开, 都不会产生太大影响, 所以基于网络编码的方案与一般的方案相比具有更好的健壮性。

然而, 基于随机线性网络编码的分布式文件存储系统在传输数据时, 节点对接收到的数据包进行编码后发送的编码数据包不光包含经编码运算的数据包, 同时还包括了编码向量。设一个大小为) 25MB的文件需要发送, 其被分割成了100个数据包, 每个数据包为256KB, 编码向g={g1, g2, g3……g100}选自一个容量为2^16 (s=16) 大小的有限域。那么为传输编码向量的额外开销为100×50 bytes/256KB=0.02%.可以看出, 传输编码向量的额外开销是可以忽略的。

但是有些因素是确实无法忽略的, 就是节点在对数据包译码的同步问题:节点能够译码的必要条件是接受到足够的编码信息才能开始译码, 这样在一些实时性苛刻的系统中, 这仍然是个难题。同时, 节点译码和编码所需要的CPU和存储器以及运算所需时间的开销都是基于随机线性网络编码的分布式文件存储系统综合性能的无法忽略的问题, 特别是当维护一个相当大的文件存储系统时。

3 结束语

近年来对于网络编码热烈的研究热潮都来源于这个新兴的领域的巨大潜力。推翻了现有通信网络中使用的路由机制“认为网络中传输的信息是不能叠加的, 只能进行存储和转发”的论断, 网络编码必将开启一个全新的计算机网络研究领域。2005年微软剑桥实验室成功开发出第一个基于随机线性网络编码的文件系统Avalanche, 虽然Avalanche并没有表现出过人的性能, 但可以看到网络编码从理论走向应用的开始。由于随机线性网络编码在带宽利用, 负载平衡上的诸多优势, 同时又具有应用简单的特点, 今后将会得到广泛应用。

参考文献

[1]Cohen B.Incentives build robustness in bit torrent[Z].In P2PEconornics Workshop, Berkeley, CA.2003.

[2]Rudolf Ahlswede, Ning Cai, Shuo—Yen Robert Li, et a1.Network information flow[J].IEEE Trans.Inform.Theory, 2000, 46 (4) :1204—1216.

[3]Sanders P, Egner S, Tolhuizen L.Polynomial time algorithms for network information flow[C].In:Proc.15th ACM Symposium on Par-allel Algorithms and Architectures, 2003.

[4]Ho T, Medard M, Shi J, et a1.On randomized network coding[C].In:Proceedings of41st Annual Allerton Conference on Communi-cation, Control。and Computing, October2003.

[5]Chou P A, Wu Y, Jain K.Practical network coding[C].Allerton Conference on Communication, Control, and Computing, Monticello, IL, October20, 2003.

[6]H0T, K0ETTER R, MEDARDM, et a1.The benefits of coding over muting in a randomized setting[c]20o3IEEE International Symposium on Information Theory (ISIT) .Japan:IEEE Press, 2003:442—45.

线性编码技术篇4

在多输入多输出天线系统(MIMO)中,对发送端的信道状态信息(CSI)的研究逐渐成为一个热点。使用发送端CSI(CSIT),可显著提高MIMO系统的性能:如增加频谱效率、减少误码率。获取CSIT的方法有互惠(reciprocity)和反馈(feedback)。在TDD系统中,通过互惠原则,利用反向信道直接估计信道;在FDD系统中,通过反馈信道将CSI反馈给发送端。由于无线信道的时变性质,不论哪种方法获取CSIT都会有一定的时间延迟,所以无法获取完美的CSIT。在实际系统中,通常使用基于信道的高阶统计信息的统计CSIT,如发送天线相关矩阵,信道均值等。

本文使用动态CSIT模型得出当前信道的条件均值和相关矩阵,提出同时基于条件均值和相关矩阵的优化方案,进一步推导出最优线性预编码器。在此基础上,提出了一种传输方案:经过正交空时分组编码(OSTBC)[1,2]的数据符号,首先通过最优线性预编码器(Precoder)进行线性变换,然后发送到无线信道;接收端使用等效信道H2(真实信道H和预编码器Precoder的乘积)对OSTBC符号进行ML解调,最终得到发送信号的估值。STBC和Precoder的结合,将使系统的性能对信道衰落和信道估计质量的变化更加鲁棒(robust)。

1 系统模型和CSIT模型

1.1 系统结构

如图1所示,系统包括M发送天线,N接收天线,假设信道H∈∁N×M(∁N×M表示N×M的复矩阵)

为准静态平坦衰落信道(准静态的含义:假设在一个码字周期内,信道保持恒定不变;不同码字周期之间的信道相互独立)。STBC码字宽度为L且使用正交编码[2]。

经过星座映射的符号流s,以B个为一组,送入STBC编码器,生成码字C∈∁L×T,其中L为码字宽度,T为码字的时间跨度;C通过线性预编码器W∈∁M×L,生成发送数据X∈∁M×T;经过信道H∈∁N×M,引入加性高斯白噪声N∈∁N×T(均值为0,方差为δ $_{n}^{2}$ ,且相互独立),得到接收信号Y∈∁N×T,如下所示:

Y=HWC+N (1)

对Y进行最大似然解调(ML),得到C的估计值 $\hat{C} \in ∁_{L \times Τ}$ :

$\hat{C} = \arg \min_{C} ∥ Y - Η W C ∥_{F}^{2} (2)$

其中,‖·‖F表示Frobenius范数。

STBC采用正交空时分组编码,正交空时分组码的设计准则请参考文献[1,2]。以2发送天线为例(Alamouti码),发送码字序列如表1所示。

其中,每一列表示某一时刻在所有天线的发送数据,每一行表示某一天线上所有时刻的发送数据。上表的码字序列,以相同的顺序排列即可得到发送码字C,码字距离定义为:

A(∁k,Cl)=(Ck-Cl)(Ck-Cl)*k≠l

对于正交空时分组码,可得:A(Ck,Cl)=μI,其中I为单位阵。

1.2 动态CSIT模型[6]

假设真实信道为H,其均值为 $\bar{Η}$ ,自协方差矩阵为R0,延时s的协方差矩阵为Rs,如下所示:

$\begin{array}{l} \bar{Η} = E [Η] \\ R_{0} = E [h h^{*}] - \bar{h} \bar{h}^{*} (3) \\ R s = E [h s h^{*}] - \bar{h} \bar{h}^{*} \end{array}$

其中小写字母表示相应矩阵的列扩展向量,(·)* 表示共轭转置。Rs越强,则表明当前时刻的信道可作为s时刻的信道的一个合理估计。假设信道具有时间上的各态历经性,且所有天线对之间具有对等性,则Rs和R0的关系可表示为:

Rs=ρR0 (4)

其中相关系数ρ可建模为0阶Bessel函数,其参数为多普勒频移和时延[3]。

以FDD系统为例,接收端根据导频序列进行信道估计,得到当前时刻(t)的信道H的估计值 $\tilde{Η}$ ;然后通过反馈信道将 $\tilde{Η}$ 反馈给发送端,发送端得到进一步恶化的信道估计值 $\hat{Η}$ 。首先,做一个合理的假设:接收端估计值 $\tilde{Η}$ 是精确无误的,且反馈的时候除了延时,不引入其它反馈误差,即:

$\hat{Η} = \tilde{Η} = Η (5)$

利用MMSE估计理论[4],在已知 $\hat{Η}$ 的条件下,下一时刻(t+Δt)的信道HΔ的条件均值和条件协方差可表示如下:

$\begin{array}{l} \bar{Η} = ρ \hat{Η} \\ R e = (1 - ρ^{2}) R_{0} (6) \end{array}$

注意:式(3)中自协方差矩阵可表示为R0=R $_{r}^{Τ}$ ⨂Rt,其中⨂表示Kronecker乘积。研究表明,假设接收端天线相互独立,并不影响系统性能。因此,本文假设Rr为单位矩阵,用Rt完全描述R0,相应的,可用下列 $\bar{R}$ t代替Re:

$\bar{R}_{t} = (1 - ρ^{2}) R_{t} (7)$

因此,HΔ的一个可能实现可表示为:

$\begin{array}{l} Η_{Δ} = \bar{Η} + Η_{w} \times \bar{R}_{t}^{1 / 2} = ρ \hat{Η} + Η_{w} \times \\ \sqrt{(1 - ρ^{2})} R_{t}^{1 / 2} (8) \end{array}$

其中,Hw为i.i.d矩阵,下文中为书写方便,省略HΔ中的下标,记为Η。

2 最优线性预编码器

2.1 性能准则

成对码字错误概率(PEP),也即“发送码字为Ck,解调为Cl”的概率即可表示为下列(9)式(式中k≠l,下文中类似处均表示k≠l);对式(9)描述的事件进行合并,可得“发送码字为Ck,解调错误”的概率,如下(10)式:

式(10)对发送码字求均值,可得“发送任意码字,解调错误”的概率Pe,其中Pk表示发送码字Ck的概率;Pe对信道H求均值,即可得到“平均码字错误概率” $\bar{Ρ}$ e:

$\begin{array}{l} Ρ e = E c [Ρ e (C)] = \sum_{k} Ρ e (C_{k}) \times Ρ_{k} (11) \\ \bar{Ρ} e = E_{Η} [Ρ e] (12) \end{array}$

本文的研究目标是最小化平均码字错误概率 $\bar{Ρ}$ e,由此建立如下优化问题:

subject to tr(WW*)=Pt

本文使用PEP的Chernoff边界,推导出 $\bar{Ρ}$ e的一个上界。可以证明最小化该上界,在很大程度上等价于最小化 $\bar{Ρ}$ e[7]。PEP的Chernoff边界可表示为:

$\begin{array}{l} Ρ (C_{k} \to C_{l}) \leq \exp (- \frac{∥ Η W (C_{k} - C_{l}) ∥_{F}^{2}}{4 δ_{n}^{2}}) = \\ \exp (- \frac{t r (Η W (C_{k} - C_{l}) (C_{k} - C_{l})^{*} W^{*} Η^{*})}{4 δ_{n}^{2}}) (14) \end{array}$

对于正交STBC系统,码字距离矩阵A=(Ck-Cl)(Ck-Cl)*=μIL,其中IL表示L×L的单位矩阵。代入式(14)可得:

$Ρ (C_{k} \to C_{l}) \leq \exp (- \frac{μ_{0} \times t r (Η W W^{*} Η^{*})}{4 δ_{n}^{2}}) (15)$

其中, $μ_{0} = \min_{A} μ$ 表示STBC的最小码字距离。

根据动态CSIT模型,由式(6),(7),(8),可得下一时刻信道H的概率密度为:

$Ρ (Η_{| C S Ι Τ}) = \frac{\exp {- t r [(Η - \bar{Η})^{*} \bar{R}_{t}^{- 1} (Η - \bar{Η})]}}{π^{Ν Μ} \det (\bar{R}_{t})^{Ν}} (16)$

将(15),(16)代入式(12),可得 $\bar{Ρ}$ e的一个上界:

$\begin{array}{l} \bar{Ρ} e \leq (Ν c - 1) \times \frac{\det (\bar{R}_{t})^{Ν}}{\det (Ψ)^{Ν}} \times \exp {t r (\bar{Η} Ψ^{- 1} \bar{Η}^{*} - \\ \bar{Η} \bar{R}_{t}^{- 1} \bar{Η}^{*})} (17) \end{array}$

其中,Nc为码字数量, $Ψ = k * \bar{R}_{t} W W^{*} \bar{R}_{t}^{*} + \bar{R}_{t} ‚ k = μ_{0} / 4 δ_{n}^{2}$ 。对式(17)的右半边求对数并忽略常数项可得:

l=tr $(\bar{Η} Ψ^{- 1} \bar{Η}^{*}) - Ν \log (\det (Ψ)) (18)$

引入一个新变量:

$Ω = \bar{R}_{t}^{- 1} Ψ \bar{R}_{t}^{- 1} - \bar{R}_{t}^{- 1} = k * W W^{*} (19)$

由此,建立如下的新优化问题:

式(20)中条件(a)对应发送功率限制,条件(b)要求Ω必须为非负定矩阵,因为Ω=k*WW*。

2.2 最优线性预编码器

式(20)的拉格朗日表达式为:

$\begin{array}{l} Γ = t r (\bar{Η} Ψ^{- 1} \bar{Η}^{*}) - Ν \log (\det (Ψ)) + \\ τ (t r (Ω) - k) (21) \end{array}$

其中τ为拉格朗日乘子。对Γ求Ψ的偏导可得[5,8]:

$\begin{array}{l} \frac{\partial Γ}{\partial Ψ} = - Ψ^{- 1} \bar{Η}^{*} \bar{Η} Ψ^{- 1} - Ν Ψ^{- 1} + τ \bar{R}_{t}^{- 2} \\ \frac{\partial Γ}{\partial Ψ} = 0 \Rightarrow Ψ = \frac{1}{2 τ} \bar{R}_{t} \times {Ν Ι_{Μ} + (Ν^{2} Ι_{Μ} + 4 τ \bar{R}_{t}^{- 1} \bar{Η}^{*} \\ \bar{Η} \bar{R}_{t}^{- 1})^{1 / 2}} \times \bar{R}_{t} (22) \end{array}$

理论上,通过功率限制条件tr(Ω)=kPt可求出τ,把τ代回式(22),即可求出Ψ和Ω,最终求出W。引入功率限制条件:

$t r (Ω) = t r (\bar{R}_{t}^{- 1} Ψ \bar{R}_{t}^{- 1} - \bar{R}_{t}^{- 1}) =$

$t r (\frac{Ν Ι_{Μ} + (Ν^{2} Ι_{Μ} + 4 τ \bar{R}_{t}^{- 1} \bar{Η}^{*} \bar{Η} \bar{R}_{t}^{- 1})^{1 / 2}}{2 τ} - \bar{R}_{t}^{- 1}) = k Ρ_{t} (23)$

引入一个新变量:

$\prod = \frac{(Ν^{2} Ι_{Μ} + 4 τ \bar{R}_{t}^{- 1} \bar{Η}^{*} \bar{Η} \bar{R}_{t}^{- 1})^{1 / 2}}{2 τ} - \bar{R}_{t}^{- 1}$

对∏进行特征值分解(evd),并使用恒等式tr(A)=sum(eig(A)),推导可得 (24)式:

$t r (Ω) = \sum_{i = 1}^{Μ} (\frac{Ν}{2 τ} + λ_{i}) = k Ρ_{t} (24)$

其中λi为∏的特征值,且假设λ1≤λ2≤…≤λM。事实上,λi随着τ的变化而变化,应写为λ(τ)i更加恰当,本文中为书写方便,简记为λi。

虽然从式(24)中推导τ的闭式解非常困难,但是通过牛顿逼近法或其它的数值方法很容易求出τ的数值解,从而求出Ω。但是,上述所求的Ω并不能保证非负定。因此,本文使用一种迭代运算,如果所求Ω不满足非负定,则将Ω进行降秩处理:将其最小的特征值强制为0,然后重新计算,直到Ω保持非负定。首先将式(24)左半部分记为新函数变量:

$f (n, τ) = \sum_{i = n + 1}^{Μ} (\frac{Ν}{2 τ} + λ_{i}) n = 0, 1, \dots, Μ - 1 (25)$

容易看出,f(n,τ)表示Ω的M-n个最大特征值之和。引入f(n,τ),迭代算法如下所示:

Initialization:

Post-process:

其中,n用于标示Ω中零特征值的数量,θi即为Ω的特征值,θi=0表示关闭该通道。该算法具有很强的适应性,不受发送天线数目或者STBC码字宽度变化的影响。计算出Ω之后,对其做特征值分解ΩV=VΛ,其中V为特征向量矩阵(容易证明V是酉矩阵),Λ为特征值组成的对角阵,然后对Ω进行重组 $Ω = V \tilde{Λ} V^{- 1} = V \tilde{Λ} V^{*}$ 。根据式(19)可得:

$W = \frac{1}{\sqrt{k}} V \tilde{Λ}^{1 / 2} \hat{V}^{*} (26)$

其中 $\hat{V}$ 用于匹配STBC的码字距离矩阵A。对于正交STBC,A为单位阵(或者乘一个标量),所以 $\hat{V}$ 也为单位阵,可以忽略。由此,最优的线性预编码器可表示为:

$W_{o p t} = \frac{1}{\sqrt{k}} V \tilde{Λ}^{1 / 2} (27)$

3 性能仿真

本节对上文所推导的线性预编码器及所提出的传输方案(PS:Proposed Scheme)进行性能仿真,并与以下三种系统进行比较:传统的空时分组码系统(CS:Conventional STBC)、传统的波束赋型系统(CB:Conventional Beamforming)、以及文献[7]提出的预编码系统(GS:George Scheme)。采用图1所示系统结构,假设天线阵列为ULA(uniform linear antenna),则信道的相关矩阵可用Hermitian矩阵表示,且假设接收天线之间相互独立;采用的信道为准静态平坦衰落信道,即一个码字周期内恒定不变,不同码字周期之间相互独立;接收端采用最大似然解调,解调使用的等效矩阵为信道与线性预编码器的乘积。如无特殊说明,以下仿真系统均假设发射天线数为2,接收天线数为1,STBC采用Alamouti码,数据符号采用BPSK调制。

首先对PS,CS,CB的性能进行比较,分别比较了不同CSIT质量下三者的性能;然后对PS,GS的性能进行比较,分别比较了不同天线相关系数下两者的性能;最后对PS性能随CSIT质量的变化进行了分析。

图2比较PS,CS,CB的性能。分别对CSIT质量ρ为0.1, 0.7, 0.99,发射天线相关系数为0.95的情况进行了仿真(从左到右依次对应图(a)、图(b)、图(c))。由图(a)中可以看出,当ρ比较低时(例如0.1),随着SNR的增大,CB相对于CS的性能增益逐渐下降,当SNR超过10.5dB时,CB性能甚至比CS还差,即ρ比较低且SNR较高时,传统的波束赋型技术的性能甚至比不需要CSIT的传统STBC性能还要差,由此可见,传统的波束赋型技术对ρ比较敏感。而本文所提的方案PS,在SNR较低时,性能接近CB方案;在SNR较高时,性能接近CS方案,之前的理论分析表明当SNR较高时,PS的性能接近等功率分配的多波束赋型系统,而等功率分配的多波束赋型系统(级联STBC)与传统STBC系统的性能完全等价。图(b)和(c)可以看出,随着ρ的提高,CB相对于CS的增益逐渐增大,即使SNR比较高时,CB相对于CS仍然有较高增益,此时,本文所提的PS方案依然优于CB与CS系统。图(c)可近似认为完美CSIT,此时PS和CB性能均近似于理想波束赋型系统。

图3比较PS与GS的性能,分别对天线相关系数为0和0.95,CSIT质量为0.1的情况进行了仿真。注意:文献[7]中的预编码系统仅仅适用于发送天线不相关的情况,如果天线之间存在相关性,将对其性能造成衰减。由图(a)中可以看出,当发送天线不相关时,本文所提的PS与[7]中的GS方案性能几乎完全相同;图(b)中当发送天线间高度相关时(例如0.95),此时GS方案的性能急剧下降,甚至比CB性能还要差,而本文所提方案性能依然稳健。

图4分析了PS的性能随CSIT质量的变化关系。由图可见,当CSIT质量比较低时,CB性能急剧下降,甚至比不需要CSIT的传统STBC的性能还要差很多,而本文所提的方案对CSIT质量的变化保持鲁棒,当CSIT质量比较低时,性能趋向于传统的STBC系统,当CSIT质量较高时,性能趋向于传统的波束赋型系统,当CSIT近似完美时,性能收敛于理想的波束赋型系统。

4 结束语

利用发送端信道估计值,信道估计质量以及发送天线相关矩阵,建立动态CSIT模型;使用PEP的Chernoff边界和信道的条件概率密度(基于动态CSIT模型),推导出平均码字错误概率Pe的一个上界。通过最小化该上界,推导出最优线性预编码器。提出空时编码和最优线性预编码器级联的传输方案,该方案综合了传统的波束赋型系统和传统的空时编码系统的优点,使系统的性能对信道衰落和CSIT质量更加鲁棒(robust)。仿真结果很好地吻合理论分析,并且显示了良好的性能增益和鲁棒性。

摘要：使用一个基于统计信息的CSIT模型:动态CSIT模型(dynamic CSIT model)。首先根据最小化平均误码率Pe的设计准则,建立凸优化问题,通过变量代换,使用标准的凸优化算法推导出最优的线性预编码器。在此基础上,提出一种正交STBC和线性预编码相结合的传输方案。仿真结果显示,该方案可获得良好的性能增益和强健的鲁棒性。

关键词：多入多出,线性预编码,空时分组码

参考文献

[1]Alamouti S M.A simple transmit diversity technique for wireless com-munications[J].IEEE J.Sel.Areas Commun.,1998,16:1451-1458.

[2] Tarokh V,Jafarkhani H,Calderbank A R.Space-time block codes from orthogonal designs[J].IEEE Trans. Inf. Theory,1999,45(5)1456-1467.

[3] Jakes W.Microwave Mobile Communications[M].IEEE Press, 1994.

[4] Kailath T,Sayed A,Hassibi H.Linear Estimation[M]. Prentice Hall, 2000.

[5] Van Trees H L.Optimum Array Processing[M].Part IV of Detection, Estimation and Modulation Theory. New York: Wiley, 2002.

[6] Vu M,Paulraj A.MIMO Wireless Precoding[J].IEEE Signal Proce-ssing Magazine, Feb 2006.

[7]J ngren G,Skoglund M,Ottersten B.Combining beamforming and or-thogonal space-time block coding[J].IEEE Trans.Inf.Theory,2002,48(3):611-627.

线性编码技术篇5

文中小写和大写的黑体字母分别表示向量和矩阵, 分别表示转置、共轭转置、矩阵的逆和迹, 和分别表示矩阵的Frobenius范数和向量的2范数, 表示的单位矩阵。

1 系统模型

这一章节本文对一个下行平稳衰落信道的单小区模型以及RZF预编码给出了定义, 基站端配备根天线, 接收端为K个单天线的用户。表示复数的集合为, 第k个用户的接收信号表示为:

假设基站端使用线性预编码器, 表示预编码矩阵向量, 为第k个用户的数据符号, 代表基站和第k个用户间的随机信道矩阵向量, 表示第k个用户的加性高斯噪声, 为接收端噪声方差, 信道考虑使用瑞利慢衰落信道模型。

2 基于SSOR的规则化破零 (RZF) 预编码

2.1 规则化破零 (RZF) 预编码

本文假设当天线数和用户数增大时, 总的发射功率不变。由文献[1]可得RZF预编码矩阵可表示为:

为功率归一化参数, 系数的根据不同的信道状态信息CSI进行选择, 对公式 (2) 中求逆的部分尺寸为K×K, 当K的数字很大时, 对该部分求逆复杂度过高。对大规模MIMO来说, 由于其信道具备渐进正交的特性, 因此可以设计一种低复杂度的预编码方案来解决这个问题。

2.2 基于对称逐次超松弛 (SSOR) 预编码算法

表示迭代次数, 表示迭代的初始值, 为了不失一般性通常选取零向量。为松弛参数, 对收敛性和收敛速率十分重要。

2.3 松弛参数的选择

2.4 计算复杂度分析

在衡量总的复杂度上, 由于乘法计算相比其他计算更为复杂, 因此, 本文根据乘法计算的次数来评估计算复杂度。由2.2可知, 基于SSOR的预编码算法的复杂度可以由2个部分组成, 解分别为:

设计一种自适应的迭代方法, 表示第次迭代后相比于第次的变化率, 当Y的值大于设定的门限值时, 说明还有优化空间。当Y的值小于设定门限值时, 停止迭代。i=2, 本文所提算法复杂度为4K2+4K, 相比Neumann的预编码方法[3]的3K2-K相差不大。当3<i<5时, SSOR预编码复杂度分别为6K2+6K, 8K2+8K, 10K2+10K相比较Neumann预编码的K3, 2K3-K2, 3K3-2K2有一个量级的提升。

3 结论

本文将设定为阈值, 当迭代次数为5次时, 停止迭代, 比较了迭代次数为2到5次时2种方法的区别, 由上述数据可得, 当迭代次数时, 基于Neumann的预编码计算复杂度为, 对RZF预编码的复杂度改善并不明显。而对任意的迭代次数来说, 基于SSOR的预编码的计算复杂度都是。当迭代次数越来越大, 本文提出的基于SSOR的预编码方法通过迭代的方式, 避免了大尺寸矩阵的求逆, 相比基于Neumann的预编码方法降低了一个量级的复杂度。同时, 自适应的迭代方法, 也避免了过多迭代带来的计算开销以及迭代不够造成的性能缺失。

摘要：大规模多输入多输出系统 (Massive MIMO) 由于天线数和用户数太大, 导致预编码矩阵在求逆是复杂度过高。为了降低复杂度, 本文提出了一种基于对称逐步超松弛 (SSOR) 的线性预编码方案, 相比传统的规则化迫零 (RZF) 预编码方案, 本文所提的方案在没有任何性能损失的情况下可以降低一个量级的运算复杂度, 为了保证所提SSOR预编码方案的性能, 提出一种仅依靠天线配置的简单的量化松弛参数。

关键词：大规模MIMO,规则化迫零预编码,对称逐步超松弛预编码,计算复杂度

参考文献

[1]J.Hoydis, S.ten Brink, and M.Debbah.Massive MIMO in the UL/DL of Cellular Networks:How Many Antennas Do We Need?[J].IEEE J.Sel.Areas Commun., 2013 (2) :160-171.

[2]A.Björck.Numerical methods in matrix computations[J].Texts in Applied Mathematics, 2015 (6) :910-916.

[3]S.Wagner, R.Couillet, M.Debbah, et al.Large System Analysis of Linear Precoding in MISO Broadcast Channels with Limited Feedback[J].IEEE Trans.Inf.Theory, 2012 (7) :4509-4537.

线性编码技术篇6

近年来, 多用户MIMO系统由于其极高的频谱效率而受到广泛的关注。与采用非线性预编码器/译码器的传输策略相比, 基于线性预编码器/译码器的传输方案具有更小的复杂度和更好的灵活性。为了设计最优的线性预编码器/译码器, 一种常用的设计准则是在发射功率受限的条件下最小化和均方误差 (sum-MSE) 。针对MIMO多址接入信道, 文献[1,2]给出了sum-MSE最小的设计方案。然而, 在MIMO下行链路中, 由于各用户信号相互干扰而使得该问题变成难以解决的非线性和非凸性的优化问题。文献[3]指出该问题可以利用运算复杂度很高的优化算法—序列二次规划 (SQP) 算法来解决。针对MISO下行链路, 文献[4]根据上行、下行链路MSE的对偶性, 将非凸的下行问题转化为对偶的上行问题, 通过解凸性的上行问题来最终得到下行问题的最优解。文献[5]将上述算法推广到MIMO下行链路中。上面提出的算法全部都针对系统和功率受限的情况。针对每个用户的发射功率单独受限的情况[3], 提出了一种启发式的联合优化算法。虽然该算法只能收敛到局部最小值, 但在最大空间分集的情况下它能有效地逼近SQP算法的性能。该方法最大的缺陷是:在收、发端满载时系统性能将极度恶化。

针对文献[3]中算法的缺陷, 本文提出了一种新的设计方案。该方案首先将多用户下行信道进行正交化, 然后通过独立地解各个等效单用户MIMO信道中的MMSE问题来获得sum-MSE最小化的近似解。与文献[3]中的算法相比, 本方案不但具有较低的运算复杂度, 而且能极大地提高系统在满载时的性能, 从而有效地增加系统的总吞吐量。

1 系统模型和信道模型

考虑如图1所示的MIMO下行链路系统, Lk×1的数据符号矢量xk经Nt×Lk的预编器Bk线性处理后相互叠加, 然后传送至具有Nt根天线的基站同时发射给k个用户, 每个用户终端配备Nrk根天线。Lk表示同时向用户k传输的并行子数据流的个数。假设各用户的数据符号相互独立且能量为一, 即:其中+表示转置共厄。当每个用户的功率限制为P/K时, 预编码矩阵Bk应满足约束条件:tr (BkB+k) ≤P/K。基站到用户的信道用Nrk×Nt的复数矩阵Hk来表示。在平坦瑞利衰落假设下, Hk的元素是均值为零, 方差为1的独立同分布的复高斯随机变量 (CGRV) , 即Hk (i, j) :CN (0, 1) 。用户k的接收信号矢量经Lk×Nrk维的译码器A+k处理后得到xk的估计值xi

undefined

nk是在用户k处Nrk×1的高斯白噪声矢量, 其中每个元素也是独立同分布的CGRV, 均值为零, 方差为σundefined。nk的相关矩阵为E (nkn+k) =σundefinedINrk。不失一般性, 假设undefinedundefined

2 线性预编码器和译码器的设计

2.1 最优线性预编码器和译码器的设计

为了保证问题的可解性, 首先引入如下两个约束:

undefined

用户k接收信号的均方误差 (MSE) 矩阵可以表示为:

undefined

假设各个用户具有相同的发射功率约束, 则对应的sum-MSE最小化问题可以描述为

undefined

虽然问题 (5) 与单用户MIMO信道中的MSE最小化问题具有类似的形式, 但由于该问题的目标函数是所有用户的预编码器和译码器的非凸性函数, 因此很难得到它的全局最优解。文献[3]中提出的联合优化算法可以中等的复杂度得到该问题的局部最优解, 然而在Lk>1的情况下其性能恶化十分严重。为了进一步减小计算复杂度并改善Lk>1时的系统性能, 本文提出一种新的次优化方案。

2.2 本文提出的设计方案

本文所提出方案的基本思想是:利用信道正交化技术将相互干扰的MIMO下行信道分解成多个独立的等效单用户MIMO信道;然后在每个等效的MIMO信道上利用MMSE准则来设计各个用户的预编码/译码器, 从而得到原问题的近似解。

令Bk预编码器可以写成Bk=VkTk。其中undefined是矩阵undefined的零空间, 即:Vk=nullspace (undefinedk) 。这样就使得HjVk=0 (j≠k) 且式 (1) 可以写成:

undefined

这样一来, 原来相互干扰的MIMO下行链路被分解成K个互不干扰的等效单用户MIMO信道, 其中第k个等效MIMO信道的信道矩阵为undefined。接下来, 就可以通过解K个等效单用户MIMO信道上的MMSE问题来设计Ak和Tk。也就是说, 通过解K个等效的单用户MMSE问题来得到问题 (5) 的近似解。

现在来看等效单用户MIMO信道上的MMSE问题。假设Tk已经确定, 则最优的译码器为线性MMSE接收机:

Aundefined= (HkVkTkT+kV+kH+k+Rnk) -1HkVkTk (7)

将式 (7) 代入式 (4) 并利用矩阵求逆引理[6], MSEk可以重写成:

MSE′k= (ILk+T+kV+kH+kHkVkTk) -1 (8)

因此, 第k个单用户MIMO信道上的MMSE问题可以描述为:

undefinedtr[MSE′k]s.t. tr[TkT+k]≤P/K, k=1, …, K (9)

利用多级注水算法[7]可以得到最优的Tk:

Tundefined=UkΣk (10)

其中, undefined由V+kH+kHkVk的undefined个最大特征值对应的特征向量组成。undefined中除右主对角线位置以外的其余位置都为零。其中,

σundefined= (μundefinedλundefined-λundefined) + (11)

式中, λk, i是V+kH+kHkVk的undefinedk个按升序排列的最大的特征值, μk是满足tr[TkT+k]=P/K的注水电平。式 (11) 就是P/K在λk, i上的多级注水功率分配。

在平坦瑞利衰落和 (2) - (3) 式的假设条件下

根据文献[6], Tundefined将第k个单用户MIMO信道分解成Lk个并行的标量信道:

undefined

式中, wk, i是归一化的白高斯噪声。这样, 第k个单用户MIMO信道上的第i个子数据流的接收信干噪比 (SINR) 为:

将式 (11) 代入 (15) ,

不难发现, 本文提出的方案最终将原来的MIMO下行矢量信道分解成undefined个标量信道。因此, 总的功率P可以在λk, i上进行注水分配。这样的功率分配方式通常为各用户分配不同的发射功率, 得到更小的和MSE。但是, 仿真结果显示, 这样的功率分配与本文提出的方案的差距仅仅在低P时才明显, 当P逐渐增加时它们之间的差距越来越小。

3 仿真结果

在本节中, 比较如下设计方案的性能:

①Joint Optimization:传统的联合优化算法[3]。

②Proposed Sch. (equal power) : 本文提出的基于功率平均分配的设计方案。

③Proposed Sch. (waterfill) :本文提出的基于注水功率分配的设计方案。

为了简单起见, 采用QPSK的调制方式且不考虑信道编码。

假设[Nt, Nrk, K, Lk]=[6, 2, 2, 2], 图2和图3分别比较系统在接收端满载的情况 (Nrk=Lk) 下联合优化算法和本文方案的BER与和MSE性能。由图可见, 正如文献[3]所描述的那样, 联合优化算法在接收端满载时系统性能很差, 而本文提出的方案在发射功率提高时BER与和MSE逐步减小, 虽然在低发射功率区域, 本文的方案要略差于联合优化算法。平均功率分配和注水功率分配的差别并不明显。

假设[Nt, Nrk, K, Lk]=[6, 2, 3, 2], 图4和图5分别比较系统在收、发两端都满载的情况下undefined和Nrk=Lk) 联合优化算法和本文方案的BER与和MSE性能。可以看到, 在总发射功率较低时, 本文的方案略差于传统的联合优化算法, 但当发射功率逐渐增加时本文的方案要远远优于传统的联合优化算法。另外, 注水功率分配要优于平均功率分配, 但是当发射功率逐渐增加时它们之间的差距逐渐减小。

4 结束语

针对多用户MIMO下行链路中的sum-MSE最小化问题, 传统的联合优化算法具有较高的复杂度, 而且当系统满载时性能变差。本文利用信道正交化技术和单用户MMSE算法得到了sum-MSE最小化问题的近似解。仿真结果表明, 在系统满载的情况下本文提出的方案明显优于传统的算法。

摘要：研究多用户MIMO下行链路中最小和均方误差意义下线性预编码器/译码器的设计问题。针对该非线性、非凸性的优化问题, 传统的联合优化算法性能有限且复杂度较高。提出一种新的设计方案。该方案首先利用信道正交化技术将MIMO下行信道分解成多个并行的等效单用户MIMO信道, 然后通过解这些等效MIMO信道上的单用户均方误差最小化问题来获得和均方误差最小问题的近似解。仿真结果显示, 该方案的性能要优于传统的联合优化算法。

关键词：MIMO,线性预编码器/译码器,最小均方误差

参考文献

[1] Jorswiech E, Boche H.Transmission strategies for the MIMO MAC with MMSE receiver: Average MSE optimization and achievable individual MSE region[J].IEEE Trans. On Signal Processing, Special Issue on MIMO Wireless Communication, 2003, 51 (11) :272-2881.

[2]Serbetli S, Yener A.Transceiver optimization for multiuser MIMO sys-tems[J].IEEE Trans.On Signal Processing, 2004, 52 (1) :214-226.

[3]Tenenbaum J, Adve R S.Joint multiuser transmit-receive optimizationusing linear processing[C].IEEE International Conference on Commu-nications, 2004, 1:586-592.

[4]Schubert M, Shi S, Boche H.Downlink sum-MSE transceiver optimiza-tion for linear multi-user MIMO systems[C]//Proc.39th Asilomar Con-ference on Signals, Systems, and Computer, CA USA, Nov.2005.

[5] Khachan A M, Tenenbaum A J, Adve R S.Liner processing for the downlink in multiuser MIMO systems with multiple data streams[C]//IEEE Intl. Conf. on Commun., June. 2006.

[6] Golub G H, Loan C F V.Matrix Compuations[M].3rd ed.Baltimore, MD: John-Hopkins Univ. Press, 1996.

网络编码技术研究篇7

1 网络信息论和网络编码的发展

在这个信息爆炸的时代, 人们对通信的研究已经不再是局限于单一的或者一对多的上面, 而是把提升整个无线网络的整体性能作为研究重点。无线Mesh网络、无线Ad-hoc网络及无线传感器网络的出现, 可以对整个网络进行无线部署, 使其具备更高的灵活性和自主管理性。随着网络编码理论被正式提出, 且能够在短时间内得到广泛的关注。网络编码作为网络信息论当中的一个重要部分, 它的提出改变了传统网络中对数据单纯的“存储转发”传输方式。在中间节点的时候就将数据编码转发, 这样能够将中间节点的计算性能得到更充分的利用。网络编码是通过利用通信节点中相对廉价的计算资源来改善网络整体特性。图1中展示了网络编码理论与各个领域之间的有着紧密联系。

网络编码理论中明确的指出了传统实物流和信息流之间的重要差异, 并证明在单源多播网络中, 只有允许网络中间节点对需要转发的数据进行编码操作, 才能达到最大流最小割所界定的网络容量上限, 即可以实现最大组播容量。如图2所示, 如果在一个没有传延迟和处理延迟的蝶形网络中, 每条边上数字表示该信道的通信能力, 即每单位时间内传输1个单位数据。源节点需要组播两个单位的信息a、b给t1和t2。根据最大流最小割定理, S同时给t1和t2发送的组播容量则是2个单位信息。如果在节点3到节点4之间的链路上出现了信息的拥塞, 节点3不能一次将a和b同时发送出去。如图2所示, 引入网络编码后, 节点3则可以将a、b按位异或编码发送, 则可以在一个单位时间内传输融合2个单位信息的数据, 而t1和t2在接收到这段编码包后, 则可以与原始数据包再次异或, 成功解码获取另一部分原始数据信息, 从而实现最大组播容量。

2 网络编码技术

线性网络编码是网络编码算法中的一个重要部分, 其主要操作过程是将数据在有限域上进行线性组合, 其算法复杂度较低, 有利于中间节点或者目的节点对数据进行编解码操作。

2.1 编码过程

假设每个数据包有L个比特组成, 如果数据不足L比特时在末尾则用0进行填补。可以把s个连续的比特视作在有限域F2上的一个符号, 则每个数据包就是L/s维的向量。使用线性网络编码, 节点中输出的数据包是对原始数据包的线性组合, 即在有限域F2上进行相加和相乘的操作。

假设P1, P2, …, Pn是由一个或多个节点发出的n个原始数据包。在线性网络编码中, 每个数据包都附有编码系数向量用该编码向量的组合以下形式的编码包X:

数据包中的每个符号都是需要进行编码, 即:

其中X (k) 和Pi (k) 分别是X和Pi中的第k个符号。编码的系数将会存储在数据包中, 目的节点用其进行解码。如公式 (2) 所示中, 编码节点3使用的编码有限域为F2={0, 1}, 编码系数则都为1, 只需进行按位异或就可以。

2.2 解码过程

目的节点接收到m个编码数据包, 分别为分别为其对应的编码系数向量。为了恢复出原始数据, 节点需要求解以下系统方程:

其中Pi是原始数据包。此时需要m≥n, 并且矩阵gj→中有n个以上是线性无关的, 就可以恢复出原始数据包。所以, 该方法则要求网络中传输到终端节点至少n个线性无关的编码包。通过独立的分布式算法, 使每个节点所产生随机的编码系数, 并生成线性无关的编码包, 从而达到提升目的节点的解码概率。

在无线网络中, 网络编码技术发挥了重要的作用。网络编码是需要编码节点和解码节点共同合作才能完成。网络编码的主要编码方法是线性网络编码, 在无线网络当中用线性编码方法可以有效的降低算法复杂度。网络编码改变了传统网络中间节点上“存储转发”的模式, 成为了二十一世纪通信领域中重要的研究方向之一。

参考文献