一种应用Turbo码实现分布式信源编码的方法_图文

1、一种应用 Turbo 码实分布式信源编码的算法廖希睿北京邮电大学信息与通信工程学院,北京 (100876E-mail :摘 要: 分布式信源编码利用多个信源之间的相关性, 进行独立编码减少传送的信息速率, 并通过联合译码提高信息传输的整体有效性。 讨论传统信道编码中的 Turbo 码技术在分布式 信源编码中的应用,通过优化分量编码器和交织器的结构,修改相应的非二进制译码算法, 来构建实用的高性能的分布式信源编译码结构。 并通过系统仿真该算法在满足一定可靠性的 前提下,能够有效地压缩信源速率。关键词:分布式信源编码; Turbo 码; RSC 编码器;交织器;非二进制 MAP 译码 中图分类号:

2、TN911.220 引言近年来,无线传感器网络引起了人们越来越多的重视。无线传感器网络(WSN 是指 由具有感知、 计算和通信能力的微型传感器节点通过自组织的方式构成的无线网络。 无线传 感器节点的能量受限, 不同节点数据之间的相关性、 低速率的无线信道传输, 以及从不同的 传感器节点到同一 Sink 节点的多对一的传输结构,使得二十世纪七十年代就已奠定理论基 础的分布式信源编码(Distributed Source Coding, DSC 技术重新在这一领域大放异彩。从 定义上来讲, DSC 是指对相互之间不能进行通信(故称分布式的多个传感器的相关输出 结果分别进行压缩(独立编码,并将压缩后

3、的结果发送到同一个中心节点进行联合译码。 早在 1973年, D. Slepian和 J.K. Wolf提出的离散相关信源压缩定理,就已经从理论上 证明了无损压缩时相关信源的独立编码(联合译码器的复杂度增加和联合编码同样有效。 随后, A. Wyner和 J. Ziv把这个定理推广到连续信源, 研究了联合高斯信源的有损编码, 给 出了率失真函数 2。但直到最近几年,随着 WSN 应用的出现, DSC 才再次成为异常活跃的 研究领域,研究者们开始寻找逼近理论界的实用编码。Wyner 在 1974年首先采用虚拟的信道来模拟信源 X 和边信息 Y 之间的相关性, 将 DSC 与信道编码紧密联系起来。

4、具有相关性的信源 X 和边信息 Y 可被模拟为虚信道的输入和输 出,解码器根据收到的伴随式 s 和 Y ,利用相关性来选择陪集中输入信道的码字。这使得 DSC 编码设计实际上也就是一种特殊的信道编码的设计。如使用比较先进的信道码技术比 如 Turbo 码和 LDPC 码,可以得到性能接近理论界限的分布式信源编码。Turbo 码是目前普遍应用的高性能信道编码, 由 C.berrou 等人最初在 93年提出来 4, 后 经理论分析和仿真实现证明了是性能优异的信道编码方案。 文献 5-8中对 Turbo 码在 DSC 中的应用进行了研究, 得到了一些具有启发性的成果, 但没有形成完善的结构体系。 文

5、献 5对译码器算法进行了简化,但是只适用于信道条件理想的情况;文献 6提出了分量编码器 的有限状态机(FSM 设计准则;文献 7分析了 Turbo 码应用于 DSC 的实际压缩效能;文 献 8分析了 Turbo 码和格图构造码 (Trellis-Based 与理论性能限的对比。 本文通过对 Turbo 码的分量编码器 RSC (Recursive Systemic Convolutional encoder,交织器以及编码结构相 对应的非二进制译码器的设计,实现使用 Turbo 编译码的分布式信源编码。 1 DSC-Turbo编译码方案为了说明本文提出的应用 Turbo 码的分布式信源编码的方

6、案, 首先将给出一个虚拟信道 中国 科技论文在线的概念,见图 1:Y 图 1 虚拟信道 图中实线箭头连接的是两个相关信源, 其中一个用作边信息对另一个进行压缩的编码过 程图, X 经过分布式信源编码器后得到码率最小为 (| X R H X Y =的编码比特, 传输到译码 器后利用 Y 进行联合译码得到对 X 的估计值 X 以及Y。由于X与Y是相关的信源,图中虚 线箭头连接的是一个虚拟的,假想的“相关信道”,这个信道的输入是信源X,输出是信源 Y。 Y相当于是X经过相关信道的噪声干扰后的信息。 按照信道编码理论, 如果采用系统形 式的信道编码, 信道编码的结果是原始的系统信息加上用于纠错的校验比

7、特, 这两部分信息 在信道上传送后进行信道译码, 利用校验信息对系统信息进行纠错。 在虚拟 “相关信道” 中, 由于 Y 是 X 叠加了相关噪声的结果,我们可以设想,如果对 X 进行系统形式的信道编码, 得到 X 的校验信息比特,在接收端利用这些校验比特和 Y ,对 X 进行译码,而 X 的系统信 息不进行发送,这样就能节省大量的带宽。按照这个思想,本文提出了下面的整体框图,将 Turbo 码应用于分布式信源编码,其基 本框图如图 2所示:图中可以用虚竖线隔成三部分,分别是编码、信道和译码。 Turbo 码编 码器有三部分组成:RSC 编码器,交织器和删余矩阵;译码器采用最大后验概率译码。下

8、面对这几个部分分别按 DSC 的要求进行设计和优化,构造 DSC -Turbo 编译码结构。 图 2 DSC-Turbo编译码框图 1.1分量编码器的设计 Turbo 码中分量编码器的选择对译码性能会产生很大的影响, 采用递归系统卷积 (RSC 编码器作为分量编码器可以获得更好的误码率性能。从 DSC 的实现目标考虑,我们采用码 率为 /1k k +的 RSC 编码器,即每个编码周期进入 RSC 的数据为 k 比特,经过编码后产生 1比特校验信息与原始的 k 比特信息组成编码输出。由于边信息的存在,丢弃原始的 k 比特 信息,只需要 1比特的校验信息。经过删余器,两个 RSC 交替保留校验比特

9、,最后得到的 码率为 /1k ,即将信源速率压缩到原来的 1/k 。j u k j u pj x 图 3 k/k+1 RSC编码器满足上述条件的 RSC 编码器的设计框图如图 3。设重量为 2的输入序列编码输出码字 的重量为 2d ,码字个数为 2N ,码的最小汉明距离 min d ,码字个数为 min N ,按照优化 2d , 2N , min d , min N , 3d , 3N , . 的方式(最大化 2d ,最小化 2N ,后面依此类推搜索出 最优的 /1k k +分量码编码器结构 9,例如当寄存器数量为 3, 2k =时,最优分量编码器结 构为 012(, , (13,15,17h

10、 h h =,其中的数字用八进制表示。1.2 交织器设计在把 Turbo 码应用于 DSC 的方案中,之前的设计都忽略了交织器的重要性。Turbo 码两个分量编码器通过一个交织器相连。其作用是保证分量编码器的输出不会出 现均为低重码字的情况, 均匀的分配码字能量, 对译码性能具有重要的影响。 最简单的交织 器也称为纵横交织器或者分组交织器, 它的实现最简单, 经常应用于抗信道突发错误, 基本 原理为行入列出,但是在 Turbo 编码中分组交织器的性能是最差的。 随机交织器的性能最 好,每组数据的交织均由随机控制, 但是实现复杂且同步困难。因此选择伪随机交织器, 选 定了交织长度以后, 通过搜索

11、算法找到合适的交织表, 对所有的分组都采用同样的交织方式, 并不对每个分组进行重新计算,减少了实现复杂度。我们使用 S-距离特性伪随机对称交织器,交织器的 S-距离特性或者说是扩展特性是指 在 交 织 过 程 中 相 邻 S 个 比 特 经 过 交 织 后 它 们 之 间 的 距 离 至 少 是 S 。 对 于 任 何 12112|( -( |, I i I i S i i S 均要满足12|S i i (1 其中 1( I i 和 2( I i 表示原始序列中元素的位置, 1i 和 2i 表示交织后序列中的第 1i 和第 2i 个元素。对于伪随机交织器的交织表生成,需要用到两个参数:交织长度

12、 L 和随机参数 S 。 在搜索过程中, 在 1到 L 之间随机选定第一个位置的数字, 之后在剩余的 L-1个数字中随机 选择一个数字作为下一个位置,并且判断是否符合 S-距离特性,如果符合就继续在 L-2个 数字中选择,如果不符合就撤销这次查找, 重新在 L-1个数字中随机选择。重复这一过程直 到所有的数字都分配到了 L 个新的位置上。注意,并非对所有的 L 和 S 都存在可行的分配 方案,如果没有分配出这样的组合,就需要调整 L 和 S ,增大 L 和减小 S 都可以使这个分 配方案有解。交织器的对称性是指经过同样的交织器, 可以进行交织和解交织的过程, 也就是原始信 息经过交织器后得到的

13、序列再次经过相同的交织器后就可以还原到原始的输入序列。 对称交 织器可以通过比特之间的互换位置来实现。 通过搜索同时满足距离特性和对称特性的数列就可以得到交织表。 1.3 译码器由于 DSC 中接收端可以是性能很强且没有限制的基站设备,因此译码可以使用复杂度 比较高但性能很好的软输入软输出(SISO MAP , LogMAP , SOVA 等 Turbo 码译码算法。 本文提出的 DSC-Turbo 码的码率 /1k ,与典型的移动通信中应用的 1/k 不同,需要采用非 二 进 制 的 译 码 方 法 。 典 型 的 移 动 通 信 环 境 中 , 所 使 用 的 信 道 码 编 译 码 方

14、式 为 1/k (2,3,4,. k =的 Turbo 码,对应 1比特的输入信息,产生若干比特的校验信息,同时 发送到接收端进行译码, 因此采用二进制译码算法, 每个译码周期的判决输出为一个二进制 比特。而在 DSC 中与此刚好相反,若干比特位的输入信息进行编码后只产生 1比特的校验 信息作为编码输出发送到信道中, 因此需要采用非二进制译码, 每个译码周期的判决输出为 一个非二进制数据, 共有 2k个备选符号。 传统的二进制 MAP 译码算法的推导中, 似然函数 设定11(1| ( (0| N k k N k p u y L u p u y = (2 当似然函数大于 0时判定当前译码输出为

15、“ 1” , 似然函数小于等于 0时, 判决为 “ 0” 。 在非二进制 MAP算法推导中可以令1( (| N k k L u p u i y = (3其中0,1,2,.,21k i =,根据似然函数的大小关系进行判决,似然函数值最大时对应 的 i 即为判决结果。 与二进制 Turbo 码译码相比, 非二进制 Turbo 码译码的格图分支数增加, 对于每条边(两个寄存器状态间的转化的度量计算是相同的。1.4 复杂度分析分布式信源编码的编码复杂度由编码端向译码端转移, 这一特点也是其应用于无线传感 器网络的主要原因。假定编码器帧长度为 L ,输入位数为 k ,寄存器数量为 m ,对应一帧 的数据

16、, RSC 编码器运算次数为 ( 22(1 1L T L k m k =×+ (4即运算复杂度为 ( ( T L O L =;交织器及其选址存储器占用的存储空间为2( (1log S L L L =+ (5 即存储空间复杂度为 2( (log S L O L L =,均是随着帧长度线性或者近似线性增长, 满足编码端的低复杂度的要求。由上述的分析可以看出, 本文提出的算法具有较低的节点功耗, 下面的仿真分析可以看 到在这样的低功耗的情况下实际译码性能也是很理想的。2 仿真结果2.1 两种编码方案实现的 DSC 与 Slepian-Wolf 限的比较 分布式信源编码的实现方式可以使用其它

17、优异的信道编码, 经过修改使之适用于分布式 信源编码的场合。 目前 Turbo 码和 LDPC 码被认为是性能最为优异的两种信道码, 下面将这 两种编码方案作一比较。令 Turbo-DSC 的分组长度为 510译码迭代次数为 15,仍然适用二 进制对称相关模型, 非规则 LDPC 码的分布式信源编码采用相同的分组长度和相关模型, 得 到的译码性能如下图: 图 4 Turbo-DSC与 LDPC 实现的 DSC图中 (| 0.5H X Y =为 Slepian-Wolf 定理在这个仿真条件下的理论界限。 从图中可以看 到,当码长达到一定的长度同时迭代译码的迭代次数也相应的达到一定的数值时, DS

18、C-Turbo 的性能与理论限之间只相差了 0.05dB ,稍微逊色于使用非规则 LDPC 码的分布 式信源编码方案, 后者与理论限之间的差距是 0.035dB 。 这个结论可以推广为, 以 Slepian-Wolf 定理为基础, 利用当前最新最有效的信道编码方案, 可以越来越接近分布式信源编码的理论 界限,找到更有效的,更节省速率的方法。2.2 二进制对称虚拟信道设信源 X 和边信息 Y 的相关性可以用二进制对称信道来建模, 且信道的转移概率为 p ,即 (| (| (2 H X Y H Y X h p =, 其中 ( h是二进制熵函数。 通过改变参数 p 的值来模拟 X 和 Y 的相关性,

19、从而比较不同的条件熵下的性能。假定信道为理想信道, 即校验位能够正确接收。 我们以 X 和 Y 之间的相关性 (| H X Y 为横坐标,以误比特率为纵坐标,通过改变 p 的值来说明误比特率与信源相关性之间的关 系,通过对 1000帧随机信源数据进行编译码仿真得到图 5,其中 L=400、 1200表示帧长度。中国科技论文在线 (a L=400 (b L=1200 图 5 二进制对称信道误码率性能 从图 5 可以看出，相同条件下，帧长度越大，误码率性能越好；迭代译码的迭代次数越 多，性能也越好。这与传统信道编码中的 Turbo 编译码性能特点相吻合，增加分组长度和迭 代译码的次数可以更加接近信

20、道编码的理论界限。帧长度的增加意味着编码复杂度的增加， 迭代次数的增加对应译码复杂度的增加， 为了取得比较好的编译码效果以及尽量减少编译码 复杂度，两者需要适当的选择。当分量码编码速率为 RX = 1/ 2 时， H ( X | Y RX 的范围 内，误码率曲线迅速下降，当迭代次数达到 10 次以上时，可以认为达到了数据传输所要求 的误差水平。根据 DSC 理论推导证明1，在 H ( X | Y RX 时，是可以实现无差错传输的， 图 5 的仿真结果表明本文提出的方案已经逼近了这一理论界限。 2.3 高斯信道 我们用相关信噪比来表示 X 与 Y 之间相关性， 设相关信道为高斯信道， 即Y =

21、X + U ， 其中 X 与 U 为独立的随机变量，方差分别为 就可以定义为 2 CSNR = x / u2 2 x 2 与 u ，那么 X 与 Y 的相关信噪比（CSNR） 。考虑到无线传感器网络今后的应用很可能是集中在视频监 控中，下面主要考查 DSC-Turbo 在图片处理上的性能仿真。 这里设信道为 AWGN 信道，信噪比为 SNR，即对信源 X 进行 DSC 编码的输出比特经 -6- 中国科技论文在线 过 AWGN 信道传输到接收端，信噪比为 SNR。经过有噪信道的 DSC 编码又称为信源信道 联合编码。图 6 为信源信道联合编码的示意图。实际信道为信号传输经过的现实中的信道， 相关

22、信道为相关信源之间抽象相关性的直观表现形式， 是由相关性特点得到的一个虚拟的信 道。 图 6 信源信道联合编码 假定传感器节点 X 获取了一幅位图图片 Lenna，相邻的另一个节点 Y 也获取了这个图 片，但是叠加了相关噪声 CSNR，通过把叠加过噪声的图片和经过 DSC-Turbo 编码的校验 信息（1/2 码率）发送到接收端，对原图片进行还原。假定相关信噪比为 CSNR=2dB，实际 信道信噪比是 SNR=2dB、3dB 和 4dB，得到的仿真结果如图 7： 图 7 DSC 图片处理 由图可见，经过 DSC-Turbo 编码，利用接收端获得的未编码的边信息以及经过编码的 校验信息，可以在有

23、噪信道条件下对原始信源信息进行译码还原。由于采用了 k / k + 1 的 RSC 编码器，这里设定 k =2 则只需要发送一半的数据。增加 k 的取值，可以得到更大的压 缩率，代价是增加了译码复杂度。 取 CSNR=2dB，实际信道的 SNR 分别取 2dB，3dB，4dB。图 5 中(a即为边信息 Y，是 原始图片经过了虚拟相关信道得到的。后面的(b、(c、(d是经过了 DSC 信源信道联合编译 码后得到的译码输出。可以看到按照(a、(b、(c、(d的顺序，图片的质量越来越好，说明 经过 DSC 编译码处理的信源信息可以更好的被还原，而且随着实际信道 SNR 的增大，图片 质量有明显的提高

24、。当 SNR 较小时，图片质量并不理想，但是当 SNR 增大到一定程度（例 如图 5 中的 4dB），图片基本与原始图片相同了。 从仿真结果可以看出，DSC 编译码可以显著减小信源发送的数据量，但是受信道条件 的影响较大。因为在 DSC 译码过程中，边信息 Y 和接收到的校验序列所起到的作用不同， 边信息作为辅助译码信息，是必不可少的，但是允许存在一定的失真；而校验信息作为译码 过程的主要处理对象，具有决定性的作用，更容易受到信道条件的影响。 3 结束语 本文针对无线传感器网络的应用前景和低复杂度低能耗高压缩率的需求， 提出了一个完 整的使用 Turbo 码构造 DSC 编译码过程的方案。通过

25、对 Turbo 码分量编码器，交织器，迭 代译码三个部分的重新设计，使其能够应用于 DSC 这一特定的场合。经过复杂度分析，这 -7- 中国科技论文在线 一编译码方案能够有效的降低编码端的复杂度，利用相关信源之间的相关性以较小的运算、 存贮和无线通信开销完成了 DSC 的要求。从仿真结果来看，这一编译码方案验证了 DSC 理 论推导的结果，性能上完全可以胜任实际应用的需求，在数据传输和图像（图片）传输中具 有较好的译码性能。 这一方案把复杂度由编码端转移到译码端， 实现了编码器结构简单化的 目标。 参考文献 1 Slepian D, Wolf J K., “Noiseless coding o

26、f correlated information sources” J , IEEE Trans. Inform. Theory, vol.19, no.4, pp.471-480, July.1973. 2 Wyner A, Ziv J, “The rate-distortion function for source coding with side information at the decoder” J, IEEE Trans. Inform. Theory, vol.22, no.1, pp.1-10, Jan.1976 3 Xiong Z, Liveris A D, Cheng

27、S, “Distributed source coding for sensor networks” J , IEEE Signal Processing Magazine, vol.21, Sept.2004 4 Berrou C, Glavieux A, Thitimajshima P, “Near Shammon limit error correcting coding and decoding: Turbo CodesJ”, Proc. International Conference on Communications, Geneva, Switzerland, pp.1064-1

28、070, May 23-26, 1993. 5 Hua Guogang, Chen Changwen. “Distributed source coding in wireless sensor networks”J , 2nd Intl Conf on Quality of Service in Heterogeneous Wired/Wireless Networks, pp.22-24, Aug.2005 6 Bajcsy J, Mitran P, “Coding for the Slepian-Wolf problem with Turbo codes” J, GLOBECOM01.I

29、EEE, vol.2, pp.25-29, Nov.2001 7 Aaron A, Girod B, “Compression with side information using Turbo codes” J, DCC02.IEEE, pp.252-261, Apr.2002 8 Chou J, Pradhan S S, Ramchandran K, “Turbo and trellis-based constructions for source coding with side information” J, DCC03.IEEE, pp.33-42, Mar.2003 9 Ho M S C, “Serial and parallel concatenated Turbo codes” D, PhD Thesis of School of Physics and Electronic Systems Engineering, The University of South Australia. 2000 A Scheme of Distributed Source Coding Utilizing Turbo C