精华内容
下载资源
问答
  • 信源编码和信道编码

    千次阅读 2018-12-06 15:14:59
    信源编码和信道编码的发展历程 信源编码:  最原始的信院编码就是莫尔斯电码,另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有:Huffman编码、算术编码、L-Z编码,这三种都是无损...

    一.信源编码和信道编码的发展历程

    信源编码:

        最原始的信院编码就是莫尔斯电码,另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有:Huffman编码、算术编码、L-Z编码,这三种都是无损编码,另外还有一些有损的编码方式。信源编码的目标就是使信源减少冗余,更加有效、经济地传输,最常见的应用形式就是压缩。

    相对地,信道编码是为了对抗信道中的噪音和衰减,通过增加冗余,如校验码等,来提高抗干扰能力以及纠错能力。

    信道编码:

    1948年Shannon极限理论

    →1950年Hamming码

    →1955年Elias卷积码

    →1960年 BCH码、RS码、PGZ译码算法

    →1962年Gallager LDPC(Low Density Parity Check,低密度奇偶校验)码

    →1965年B-M译码算法

    →1967年RRNS码、Viterbi算法

    →1972年Chase氏译码算法

    →1974年Bahl MAP算法

    →1977年IMaiBCM分组编码调制

    →1978年Wolf 格状分组码

    →1986年Padovani恒包络相位/频率编码调制

    →1987年Ungerboeck TCM格状编码调制、SiMonMTCM多重格状编码调制、WeiL.F.多维星座TCM

    →1989年Hagenauer SOVA算法

    →1990年Koch Max-Lg-MAP算法

    →1993年Berrou Turbo码

    →1994年Pyndiah 乘积码准最佳译码

    →1995年 Robertson Log-MAP算法

    →1996年 Hagenauer TurboBCH码

    →1996MACKay-Neal重新发掘出LDPC码

    →1997年 Nick Turbo Hamming码

    →1998年Tarokh 空-时卷格状码、AlaMouti空-时分组码

    →1999年删除型Turbo码

         虽然经过这些创新努力,已很接近Shannon极限,例如1997年Nickle的TurboHamming码对高斯信道传输时已与Shannon极限仅有0.27dB相差,但人们依然不会满意,因为时延、装备复杂性与可行性都是实际应用的严峻要求,而如果不考虑时延因素及复杂性本来就没有意义,因为50多年前的Shannon理论本身就已预示以接近无限的时延总容易找到一些方法逼近Shannon极限。因此,信道编码和/或编码调制理论与技术在向Shannon极限逼近的创新过程中,其难点是要同时兼顾考虑好编码及交织等处理时延、比特误码率门限要求、系统带宽、码率、编码增益、有效吞吐量、信道特征、抗衰落色散及不同类别干扰能力以及装备复杂性等要求。从而,尽管人们普遍公认Turbo码确是快速逼近Shannon极限的一种有跃变性改进的码类,但其时延、复杂性依然为其最严峻的挑战因素,看来,沿AlaMouti的STB方式是一种看好的折衷方向。同样,实际性能可比Turbo码性能更优良的LDPC码,从1962年Gallager提出, 当时并未为人们充分理解与重视,至1996年为MACKay—Neal重新发现后掀起的另一股推进其研究、应用热潮, 此又为另一明显示例。LDPC码是一类可由非常稀疏的奇偶校验矩阵或二分图(Bi-PartiteGrapg)定义的线性分组前向纠错码,它具有更简单的结构描述与硬件复杂度,可实现完全并行操作,有利高速、大吞吐能力译码,且译码复杂度亦比Turbo码低,并具更优良的基底(Floor)残余误码性能,研究表明,最好的非正则(Irregular)LDPC码,其长度为106时可获得BER=10-6时与Shannon极限仅相差0.13dB;当码长为107、码率为1/2,与Shannon极限仅差0.04dB;与Turbo码结构不同,这是由另一种途径向“Shannon极限条件”的更有效与更逼真的模拟,从而取得比Turbo码更好的性能。因此,“学习、思考、创新、发展”这一永恒主题中持续“创新”最为关键,MIMO-STC及Turbo/LDPC码的发展历程亦充分证实了这一发展哲理。

     

    二.信源编码和信道编码远离的简要介绍

    信源编码:

    一种以提高通信有效性为目的而对信源符号进行的变换;为了减少或消除信源剩余度而进行的信源符号变换。为了减少信源输出符号序列中的剩余度、提高符号的平均信息量,对信源输出的符号序列所施行的变换。具体说,就是针对信源输出符号序列的统计特性来寻找某种方法,把信源输出符号序列变换为最短的码字序列,使后者的各码元所载荷的平均信息量最大,同时又能保证无失真地恢复原来的符号序列。

      数字信号在传输中往往由于各种原因,使得在传送的数据流中产生误码,从而使接收端产生图象跳跃、不连续、出现马赛克等现象。所以通过信道编码这一环节,对数码流进行相应的处理,使系统具有一定的纠错能力和抗干扰能力,可极大地避免码流传送中误码的发生。误码的处理技术有纠错、交织、线性内插等。

      提高数据传输效率,降低误码率是信道编码的任务。信道编码的本质是增加通信的可靠性。但信道编码会使有用的信息数据传输减少,信道编码的过程是在源数据码流中加插一些码元,从而达到在接收端进行判错和纠错的目的,这就是我们常常说的开销。这就好象我们运送一批玻璃杯一样,为了保证运送途中不出现打烂玻璃杯的情况,我们通常都用一些泡沫或海棉等物将玻璃杯包装起来,这种包装使玻璃杯所占的容积变大,原来一部车能装5000各玻璃杯的,包装后就只能装4000个了,显然包装的代价使运送玻璃杯的有效个数减少了。同样,在带宽固定的信道中,总的传送码率也是固定的,由于信道编码增加了数据量,其结果只能是以降低传送有用信息码率为代价了。将有用比特数除以总比特数就等于编码效率了,不同的编码方式,其编码效率有所不同。

        基于层次树的集分割(SPIHT)信源编码方法是基于EZW而改进的算法,它是有效利用了图像小波分解后的多分辨率特性,根据重要性生成比特流的一个渐进式编码。这种编码方法,编码器能够在任意位置终止编码,因此能够精确实现一定目标速率或目标失真度。同样,对于给定的比特流,解码器可以在任意位置停止解码,而仍然能够恢复由截断的比特流编码的图像。而实现这一优越性能并不需要事先的训练和预存表或码本,也不需要任何关于图像源的先验知识。

      数字电视中常用的纠错编码,通常采用两次附加纠错码的前向纠错(FEC)编码。RS编码属于第一个FEC,188字节后附加16字节RS码,构成(204,188)RS码,这也可以称为外编码。第二个附加纠错码的FEC一般采用卷积编码,又称为内编码。外编码和内编码结合一起,称之为级联编码。级联编码后得到的数据流再按规定的调制方式对载频进行调制。  

      前向纠错码(FEC)的码字是具有一定纠错能力的码型,它在接收端解码后,不仅可以发现错误,而且能够判断错误码元所在的位置,并自动纠错。这种纠错码信息不需要储存,不需要反馈,实时性好。所以在广播系统(单向传输系统)都采用这种信道编码方式。以下是纠错码的各种类型:

     

        既然信源编码的基本目的是提高码字序列中码元的平均信息量,那么,一切旨在减少剩余度而对信源输出符号序列所施行的变换或处理,都可以在这种意义下归入信源编码的范畴,例如过滤、预测、域变换和数据压缩等。当然,这些都是广义的信源编码。  

    一般来说,减少信源输出符号序列中的剩余度、提高符号平均信息量的基本途径有两个:①使序列中的各个符号尽可能地互相独立;②使序列中各个符号的出现概率尽可能地相等。前者称为解除相关性,后者称为概率均匀化。

    第三代移动通信中的信源编码包括语音压缩编码、各类图像压缩编码及多媒体数据压缩编码。

     

    信道编码:

        数字信号在传输中往往由于各种原因,使得在传送的数据流中产生误码,从而使接收端产生图象跳跃、不连续、出现马赛克等现象。所以通过信道编码这一环节,对数码流进行相应的处理,使系统具有一定的纠错能力和抗干扰能力,可极大地避免码流传送中误码的发生。误码的处理技术有纠错、交织、线性内插等。

    提高数据传输效率,降低误码率是信道编码的任务。信道编码的本质是增加通信的可靠性。但信道编码会使有用的信息数据传输减少,信道编码的过程是在源数据码流中加插一些码元,从而达到在接收端进行判错和纠错的目的,这就是我们常常说的开销。

    码率兼容截短卷积(RCPC)信道编码,就是一类采用周期性删除比特的方法来获得高码率的卷积码,它具有以下几个特点:

    (1)截短卷积码也可以用生成矩阵表示,它是一种特殊的卷积码;

    (2)截短卷积码的限制长度与原码相同,具有与原码同等级别的纠错能力;                                            (3)截短卷积码具有原码的隐含结构,译码复杂度降低;

       (4)改变比特删除模式,可以实现变码率的编码和译码。

     

    三.信源编码和信道编码的区别

        信源编码信源编码的作用之一是设法减少码元数目和降低码元速率,即通常所说的数据压缩。码元速率将直接影响传输所占的带宽,而传输带宽又直接反映了通信的有效性。作用之二是,当信息源给出的是模拟语音信号时,信源编码器将其转换成数字信号,以实现模拟信号的数字化传输。模拟信号数字化传输的两种方式:脉冲编码调制(PCM)和增量调制(ΔM)。信源译码是信源编码的逆过程。1.脉冲编码调制(PCM)简称脉码调制:一种用一组二进制数字代码来代替连续信号的抽样值,从而实现通信的方式。由于这种通信方式抗干扰能力强,它在光纤通信、数字微波通信、卫星通信中均获得了极为广泛的应用。增量调制(ΔM):将差值编码传输,同样可传输模拟信号所含的信息。此差值又称“增量”,其值可正可负。这种用差值编码进行通信的方式,就称为“增量调制”,缩写为DM或ΔM,主要用于军方通信中。信源编码为了减少信源输出符号序列中的剩余度、提高符号的平均信息量,对信源输出的符号序列所施行的变换。具体说,就是针对信源输出符号序列的统计特性来寻找某种方法,把信源输出符号序列变换为最短的码字序列,使后者的各码元所载荷的平均信息量最大,同时又能保证无失真地恢复原来的符号序列.信道编码的目的:信道编码是为了保证信息传输的可靠性、提高传输质量而设计的一种编码。它是在信息码中增加一定数量的多余码元,使码字具有一定的抗干扰能力。信道编码的实质:信道编码的实质就是在信息码中增加一定数量的多余码元(称为监督码元),使它们满足一定的约束关系,这样由信息码元和监督码元共同组成一个由信道传输的码字。信源编码很好理解,比如你要发送一个图形,必须把这个图像转成0101的编码,这就是信源编码。

        信道编码数字信号在信道传输时,由于噪声、衰落以及人为干扰等,将会引起差错。为了减少差错,信道编码器对传输的信息码元按一定的规则加入保护成分(监督元),组成所谓“抗干扰编码”。接收端的信道译码器按一定规则进行解码,从解码过程中发现错误或纠正错误,从而提高通信系统抗干扰能力,实现可靠通信。信道编码是针对无线信道的干扰太多,把你要传送的数据加上些信息,来纠正信道的干扰。信道编码数字信号在信道传输时,由于噪声、衰落以及人为干扰等,将会引起差错。为了减少差错,信道编码器对传输的信息码元按一定的规则加入保护成分(监督元),组成所谓“抗干扰编码”。接收端的信道译码器按一定规则进行解码,从解码过程中发现错误或纠正错误,从而提高通信系统抗干扰能力,实现可靠通信。

    信源编码信号:例如语音信号(频率范围300-3400Hz)、图象信号(频率范围0-6MHz)……基带信号(基带:信号的频率从零频附近开始)。在发送端把连续消息变换成原始电信号,这种变换由信源来完成。

    信道编码信号:例如二进制信号、2PSK信号……已调信号(也叫带通信号、频带信号)。这种信号有两个基本特征:一是携带信息;二是适应在信道中传输,把基带信号变换成适合在信道中传输的信号完成这样的变换是调制器。

    信源编码是对输入信息进行编码,优化信息和压缩信息并且打成符合标准的数据包。信道编码是在数据中加入验证码,并且把加入验证码的数据进行调制。两者的作用完全不一样的。信源编码是指信号来源的编码,主要是指从那个接口进来的。信道编码是说的信号通道的编码,一般是指机内的电路。总的来说吧:信源编码是对视频, 音频, 数据进行的编码,即对信息进行编码以便处理,而信道编码是指在信息传输的过程中对信息进行的处理。

     

    四.信源编码和信道编码在现代社会的应用

    1.在现代无线通信中的应用:

        通信的任务是由一整套技术设备和传输媒介所构成的总体——通信系统来完成的。电子通信根据信道上传输信号的种类可分为模拟通信和数字通信。最简单的数字通信系统模型由信源、信道和信宿三个基本部分组成。实际的数字通信系统模型要比简单的数字通信系统模型复杂得多。数字通信系统设备多种多样,综合各种数字通信系统,其构成如图所示:

     

     

        信源编码是以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。

    信道,通俗地说是指以传输媒质为基础的信号通路。具体地说,信道是指由有线或无线电线路提供的信号通路。信道的作用是传输信号,它提供一段频带让信号通过,同时又给信号加以限制和损害。

    信道编码是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率或带宽。与信源编码正好相反。在计算机科学领域,信道编码(channel code)被广泛用作表示编码错误监测和纠正的术语,有时候也可以在通信和存储领域用作表示数字调制方式。信道编码用来在数据传输的时候保护数据,还可以在出现错误的时候来恢复数据。

    2.在超宽带信道中的应用

    超宽带(Ultra Wideband,以下简称UWB) [1][2]系统具有高传输速率、低功耗、低成本等独特优点,是下一代短距离无线通信系统的有力竞争者。它是指具有很高带宽比射频(带宽与中心频率之比)的无线电技术。近年来,超宽带无线通信在图像和视频传输中获得了越来越广泛的应用,它具有极高的传输速率以及很宽的传输频带,可以提供高达1Gbit/s的数据传输速率,可用在数字家庭网络或办公网络中,实现近距离、高速率数据传输。例如,利用UWB技术可以在家用电器设备之间提供高速的音频、视频业务传输,在数字办公环境中,应用UWB技术可以减少线缆布放的麻烦,提供无线高速互联。  

        联合信源信道编码(Joint Source Channel Coding,以下简称JSCC)[3][4]近几年来日益受到通信界的广泛重视,主要原因是多媒体无线通信变得更加重要。根据Shannon信息论原理,通信系统中信源编码和信道编码是分离的[5],然而,该定理假设信源编码是最优的,可以去掉所有冗余,并且假设当比特率低于信道容量时可纠正所有误码。在不限制码长的复杂性和时延的前提下,可以得到这样的系统。而在实际系统中又必须限制码长的复杂性和时延,这必然会导致性能下降,这和香农编码定理的假设是相矛盾的。因此,在许多情况下,采用独立编码技术并不能获得满意的效果,例如有严重噪声的衰落信道和(移动通信信道),采用独立编码技术不能满足要求。因此需要将信源编码和信道编码联合考虑,在实际的信道条件中获得比信源和信道单独进行编码更好的效果。其中不等差错保护是联合信源信道编码的一种, 是相对于同等差错保护而言的。在网络资源有限的情况下,同等差错保护方案使得重要信息得不到足够的保护而使解码质量严重下降。而不等差错保护根据码流的不同部分对图像重建质量的重要性不同, 而采用不同的信道保护机制, 是信源信道联合编码的一个重要应用。

    不等差错保护(Unequal Error Protection,以下简称UEP)的信源编码主要采用嵌入式信源编码,如SPIHT(Set Partitioning In Hierarchical Trees) [6],EZW,JPEG2000等,信源输出码流具有渐进特性,信道编码采用RCPC[7],RCPT等码率可变的信道编码。文章[8]中研究了在AWGN信道下的不等差错保护的性能; 文章[9]中研究了有反馈的移动信道下的多分辨率联合信源信道编码;文章[10]研究了无线信道下的图像传输,信源编码采用SPIHT,信道编码采用多码率Turbo coder的不等差错保护方案;文章[11]中研究了DS-CDMA多径衰落信道下信源编码为分层视频图像编码,信道编码采用RCPC,解决了在信源编码,信道编码以及各个层之间的码率最优分配; 文章[12]研究了3G网络下MPEG-4视频流的传输,信道编码采用 Turbo编码,提出了用TCP传输非常重要的MPEG-4流,而用UDP传输MPEG-4 audio/video ES (Elementary Streams),并且对UDP传输的码流进行UEP的方案;文章[13]研究在无线频率选择性衰落信道中将MIMO-OFDM和adaptive wavelet pretreatment(自适应小波预处理)结合在一起的联合信源信道编码图像传输。据我们的了解, 现在并无文章研究超宽带无线信道下不等差错保护方案,本文将不等差错保护联合信源信道编码应用于超宽带无线通信中, 信源部分采用基于小波SPIHT 的编码方法,而信道部分采用RCPC编码( Rate Compatible Punctured Convolutional codes) 对SPIHT输出码流按重要程度进行不等错误保护,并基于DS-UWB[14]方案提出双重不等差错保护方案, 研究了不等差错保护给图像在超宽带无线通信中的图像传输所带来性能增益。  

    采用标准LENA256×256图像进行仿真实验, 信源编码采用SPIHT算法,SPIHT 编码速率为0.5bpp, 信道编码采用码率自适应截短卷积码RCPC, 对实验图像进行同等差错保护信道编码( EEP) 和不等差错保护信道编码(UEP), 对于EEP编码采用1/ 2 码率;对于UEP 编码,其重要信息(包括头部语法及图像重要数据) 采用1/ 3码率,对图像次重要数据采用1/ 2码率进行编码,对图像非重要数据不进行编码。信道编码输出码流经过一个(Ns,1)重复编码器,对重要信息Ns取30,次重要数据Ns取20,非重要数据Ns取为10,再用一个周期为Np=Ns的伪随机DS码序列对重复编码器输出序列进行编码,最后对编码输出进行PAM调制和脉冲成形从而形成DS-UWB发送信号波形,其中脉冲参数设置为平均发射功率为-30,抽样频率为50e9,平均脉冲重复时间为2e-9,冲激响应持续时间为0.5e-9,脉冲波形形成因子为0.25e-9。DS-UWB信号经过IEEE802.15.3a CM1信道模型,接收端采用Rake接收机对接收信号进行解调,解调后的码流经过RCPC信道译码和SPIHT信源译码恢复出原始图像。

     

               CMI信道模型下Double-UEP与UEP,EEP的性能比较

    图中给出了IEEE802.15.3a CM1信道模型下双重不等差错保护(Double-UEP)与传统不等差错保护(UEP)与同等差错保护(EEP)的性能比较,其中横轴为超宽带信道中的信噪比Eb/N0,纵轴为重建图像的峰值信噪比PSNR(Peek Signal Noise Ratio)。

      由图可见,在UWB信道中,不等差错保护的性能普遍好于同等差错保护的性能,尤其是在低信噪比的时候,采用不等差错保护能够获得更大的性能增益。在高信噪比时,由于此时信道质量较好,误码率较低,图像中的重要码流基本不会产生误码,此时不等差错保护和同等差错保护性能趋于一致;而在低信噪比时,由于不等差错保护方案对图像的重要信息加入了更多的冗余,从而在不增加传输速率的情况下使图像得以更可靠的传输,提升重建图像的质量。

     

    五.信源编码与信道编码的发展前景

    信息论理论的建立,提出了信息、信息熵的概念,接着人们提出了编码定理。编码方法有较大发展,各种界限也不断有人提出,使多用户信息论的理论日趋完整,前向纠错码(FEC)的码字也在不断完善。但现有信息理论中信息对象的层次区分对产生和构成信息存在的基本要素、对象及关系区分不清,适用于复杂信息系统的理论比较少,缺乏核心的“实有信息”概念,不能很好地解释信息的创生和语义歧义问题。只有无记忆单用户信道和多用户信道中的特殊情况的编码定理已有严格的证明,其他信道也有一些结果,但尚不完善。但近几年来,第三代移动通信系统(3G)的热衷探索,促进了各种数字信号处理技术发展,而且Turbo码与其他技术的结合也不断完善信道编码方案。

    移动通信的发展日新月异,从1978年第一代模拟蜂窝通信系统诞生至今,不过20多年的时间,就已经过三代的演变,成为拥有10亿多用户的全球电信业最活跃、最具发展潜力的业务。尤其是近几年来,随着第三代移动通信系统(3G)的渐行渐近,以及各国政府、运营商和制造商等各方面为之而投入的大量人力物力,移动通信又一次地在电信业乃至全社会掀起了滚滚热潮。虽然目前由于全球电信业的低迷以及3G系统自身存在的一些问题尚未完全解决等因素,3G业务的全面推行并不象计划中的顺利,但新一代移动通信网的到来必是大势所趋。因此,人们对新的移动通信技术的研究的热情始终未减。

    移动通信的强大魅力之所在就是它能为人们提供了固话所不及的灵活、机动、高效的通信方式,非常适合信息社会发展的需要。但同时,这也使移动通信系统的研究、开发和实现比有线通信系统更复杂、更困难。实际上,移动无线信道是通信中最恶劣、最难预测的通信信道之一。由于无线电波传输不仅会随着传播距离的增加而造成能量损耗,并且会因为多径效应、多普勒频移和阴影效应等的影响而使信号快速衰落,码间干扰和信号失真严重,从而极大地影响了通信质量。为了解决这些问题,人们不断地研究和寻找多种先进的通信技术以提高移动通信的性能。特别是数字移动通信系统出现后,促进了各种数字信号处理技术如多址技术、调制技术、纠错编码、分集技术、智能天线、软件无线电等的发展。

     

    结论:

    从文中我们可以清楚的认识到信源编码和信道编码的发展布满艰辛,今天的成就来之不易。随着今天移动通信技术的不断发展和创新,信源编码与信道编码的应用也越来越广泛,其逐步的应用于各个领域,在通信系统中扮演着非常重要的角色,起到了至关重要的作用。但是,现有信息理论也存在一定的缺陷,具体表现在以下几个方面:

    1.现有信息理论体系中缺乏核心的 “实有信息”概念。

    2.适用于复杂信息系统的理论比较少。目前的狭义与广义信息论大多是起源和立足于简单系统的信息理论,即用简单通讯信息系统的方法来类比复杂系统的信息现象,将复杂性当成了简单性来处理。而涉及生命现象和人的认识论层次的信息是很复杂的对象,其中信宿主体内信息的语义歧义和信息创生问题是难点,用现有信息理论难以解释。

    3.对产生和构成信息存在的基本要素、对象及关系区分不清。如将对象的直接存在(对象的物质、能量、相互作用、功能等存在)当成信息存在;将信息的载体存在当成信息存在;将信息与载体的统一体当成信息存在;把信宿获得的“实得信息”当成唯一的信息存在,这是主观信息论。或者把信源和信道信息当成唯一的信息存在,称之为客观信息论。这二种极端的信息理论正是忽略了信息在关系中产生、在关系中存在的复杂本质。忽略了信息存在至少涉及三个以上对象及复杂关系。

    4.现有信息理论不能很好地解释信息的创生和语义歧义问题。

    5.现有信息理论对信宿实得信息的理解过于简单,没有将直接实得信息与间接实得信息区别开来。

    6.信息对象的层次区分没有得到重视。不少研究者将本体论层次的信息与认识论层次的信息混为一谈,将普适性信息范畴与具体科学,特别是技术层次(如通信、控制、计算等)的信息概念混为一谈。抓住信息的某一层次或某一方面当成信息对象的总体。

        因此,在科学技术飞速发展的今天,我们应该加强对信源编码与信道编码的了解和认识,这能让在以后的生活和学习过程中不断完善和改进现有信息论存在的缺陷,更好的应用和了解我们的专业知识,更好更快的做好自己的工作,让自己能从各方面得到满意的结果。

    展开全文
  • 卷积码译码之维特比译码算法(Viterbi decoding algorithm) 本文主要介绍了卷积码的一种译码方法——维特比译码(Viterbi decoding)。 关键词:卷积码译码 维特比译码算法 卷积码简介:点击打开链接 ==========...
    卷积码译码之维特比译码算法
    (Viterbi decoding algorithm)
           本文主要介绍了卷积码的一种译码方法——维特比译码(Viterbi decoding)。
           关键词: 卷积码译码 维特比译码算法 

           卷积码简介:点击打开链接

           ============================================================== 

           目录结构:

           1、维特比译码简介

           2、维特比译码过程

            ==============================================================


    1、维特比译码简介

           Viterbi算法是由美国科学家Viterbi在1967年提出的卷积码的概率译码算法,后来学者深入研究中证明Viterbi算法是基于卷积码网格图的最大似然译码算法。何为最大似然译码?在这里我们可以进行以下简单的理解:即根据已经接收到的信息,得到最接近编码码字的一种译码码字。得到这种码字使用的译码准则为最大似然译码。(如果觉得繁琐,第1部分可先略过)
           定义以下信号如图1所示:
           (1)发送端
           信源:u
           编码器输出编码码字:v
           (2)接收端
           译码器输入信息:r
           译码器输出:u_dec
     
    图1、经典通信系统
           译码器输出序列u_dec是u的一个估计值。译码器根据一定的译码规则,由接收序列r产生u_dec序列。由于信息序列u与码字v有对应关系,所以等效于译码器产生一个码字v的估值v’。当v‘=v是,u_dec=u。所以,当v‘不等于v时,译码出现错误。
           译码器的条件错误概率定义为:
           译码器的错误概率定义如下:
           其中接收序列r是译码前产生的,所以p(r)与译码规则无关。为了是译码错误概率最小的最佳的译码准则必须满足对所有的r使p(E|r)最小。所以有
           根据以上公式可知,对于给定的接收序列r,如果选择适合的v’,使p(v’=v|r)最大,则一定是最佳的。
    根据贝叶斯公式:
           如果发送码字的概率p(v)相同,p(r)又与译码规则无关,则
           所以,译码器如果可以选择一个估计值使得上式最大,则这种译码器称为最大似然译码。p(r|v)称为似然函数。对数似然函数则如下:
           如果码字不是等可能的,最大似然译码不一定是最佳的。在这种情况下,在决定哪个码字能使p(v|r)最大时,必须以概率p(v)对条件概率log p(ri|vi)加权。但在许多系统的接收端不知道发送码字的概率,所以最佳译码是不可能的,最大似然译码就成了可行的译码规则。
           转移概率p<1/2的二进制对此信道(BSC),接收序列r是二元的。对于卷积码,对数似然函数如下:
           其中d(r,v)是r和v之间的汉明距离。由于对所有的v,log p/(1-p) < 0且N log(1-p)是常熟,因此,对于BSC而言,最大似然译码是选择使r和v之间距离最小的v‘作为码字v。

    2、维特比译码过程

           由于最大似然译码等效于最小距离译码,因此具有最小d(r,v)累积值的路径就是log p(r|v)的最大路径,该路径被称为幸存路径。定义BM=d(ri,vi),称为分支度量值。PM称为最小累积度量值,是对所有分支度量值的累积。
           卷积码的编码过程与网格图中的一条路径对应,即输入序列的编码过程与网格图中的路径一一对应。当序列长度为x时,网格中有2^x条不同的路径和编码器的2^x种输入序列对应。在网格图中,每个状态转移的过程中都会输出编码码字。由于译码过程也建立在网格图中,并且从全零状态开始,从全零状态结束。所以,在每个符合输入的分支中,都可以计算出分支度量值。
           维特比译码算法步骤如下:
           (1)在j=L-1个时刻前,计算每一个状态单个路径分支度量。
           (2)第x-1个时刻开始,对进入每一个状态的部分路径进行计算,这样的路径有2^k条,挑选具有最大部分路径值的部分路径为幸存路径,删去进入该状态的其他路径,然后,幸存路径向前延长一个分支。
           (3)重复步骤(2)的计算、比较和判决过程。若输入接收序列长为(x+L-1)k,其中,后L-1段是人为加入的全0段,则译码进行至(x+ L-1)时刻为止。
           若进入某个状态的部分路径中,有两条部分路径值相等,则可以任选其一作为幸存路径。
           该 译码算法的核心思想在于“ 加、比、选”,务必牢记,
            指的是将每个路径的分支度量进行累积。度量的方法有汉明距或者欧式距离等方法。
            指的是将到达节点的两条路径进行对比。

           指的是选出到达节点的两条路径中度量值小的一条路径作为幸存路径。

           

           以(2,1,2)卷积码例子说明维特比译码过程:
           输入数据:u = [1 1 0 1 1]
           编码码字:V = [11 01 01 00 01]
           接收码字:R = [11 01 01 10 01]

           (2,1,2)卷积码在以上算法中的参数,x=5,L=3,k=1,j从0开始计时。


           该卷积码的编码结构如下图所示:
     
    图2.(2,1,2)卷积码编码结构图

     
    图3. 各个分支的编码输出如图所示

     
    图4. 解码步骤1

           解码步骤(1),j=0,1,2这3个时刻中计算出每个路径的分支度量值和,即汉明距离,在图中以蓝色的数字表示。比如接收序列R中的第一个符合“11”,与第一回合的两条路径中的“00”,“11”的汉明距分别为2和0,改数字被标注在每条线对应的下方或附近。
           在每个状态节点具有两条路径时,译码算法才开始根据分支度量的大小选择幸存路径,再删除其他路径。该步骤如下图所示。
     
    图5. 第一个节点的幸存路径选择

           图5. 第一个节点的幸存路径选择,由于进入状态S0的两条路径的度量值3<4,所以选择度量值为3的图中红色线为幸存路径。
     
    图6. 第二个节点的幸存路径选择

     
    图7. 第三个节点的幸存路径选择

     
    图8. 第四个节点的幸存路径选择

           至此,第一次幸存路径选择完成,现在删除其他路径,将接下来的路径的分支度量值都标注在图中,如下图示。
     
    图9. 剩余译码路径的分支度量值计算标注

           以上图中在每个节点进行比较分支度量值比较,胜出的分支度量值被标注在状态节点的上方。
           以上图中在最后一个符号的译码得出一条分支度量值最小的路径,如下图所示,该条路径即译码的最佳路径。
     
    图10. 最佳路径输出
           根据该路径得出的译码输出为【11 01 01 00 01】与例子中编码码字V相同。该码字对应的输入数据可以根据以上最佳路径实线或者虚线读出,即【1 1 0 1 1】。

           网格图中的每一条路径的编码输出matlab代码如下所示:

    clc;close all;clear
    fid = fopen('test.txt','wt');
    d1  = 0;
    d2  = 0;
    N   = 5;
    for i = 0:31
        data = dec2bin(i,N);
        for j = 1:N
            %output calculation
            x   = str2num(data(j)); 
            y1  = mod(x + d1 + d2,2);
            y2  = mod(x + d2,2);
            y   = [y1,y2];
            %shift
            d2 = d1;
            d1 = x;
            fprintf(fid,'%d%d ',y1,y2);
        end
        fprintf(fid,' %s\n',dec2bin(i,5));
        d1 = 0;
        d2 = 0;
    end
    fclose('all')



    展开全文
  • 无失真信源编码2

    2021-07-10 20:38:58
    渐进等同分割性质::一个随机过程是非等概分布的,对它进行定长分割,把随机过程符号切割成段,每段的长度逐渐越来越大,结果发现:当长度足够大是,那么每一段的出现可能组合是等概分布的(段长足够大时,每一段...

      信源无失真编码实质:熵总量是不变的,一个信源的分布也是不能改变的,我们能做的只是通过分组的手段,定义信道能传输的符号并且它和信源原始进行一一映射,使得编码后每一个符号尽可能携带更多的信息量,把平均码长缩短,达到压缩信源的目的。
      渐进等同分割性质:一个随机过程是非等概分布的,对它进行定长分割,把随机过程符号切割成段,每段的长度逐渐越来越大,结果发现:当长度足够大是,那么每一段的出现可能组合是等概分布的(段长足够大时,每一段出现的可能的组合几乎呈相同概率发生).
    典型序列:假设一个信源的符号有x个,段长为n,那个所有可能的字母符号组合为:x^{n},但是里面的典型序列(经常出现)却大约有:2^{nH(X)}个,是很小的一个子集,但是:在段长足够长,典型序列几乎一定会出现,也就是非典型序列几乎不会出现,而且:每一个典型序列(典型集的元素)几乎成等概分布,也就有了无失真定长编码的基础。


    目录

    一:信源编码基本概念

                      信源编码的作用和目的

    二:定长无失真信源编码定理

    三:变长无失真信源编码 

    四:几种码

    五:前缀码约束条件

                    kraft不等式


    一:信源编码基本概念

    信源编码:将信源符号序列按一定数学规律映射成码符号序列的过程
    具体来说:将信源符号集中的符号s_{i}(或长为N的信源符号序列)映射成码符号序列w_{i},每个w_{i}是由长度为l_{i}的码符号x_{i}组成。

     信源编码的作用和目的

    作用:1:使得信源符号适合信道的传输2:用尽可能少的符号来传递信源信息,提高有效性。
    目的:通过压缩信源的冗余度来提高通信有效性
    冗余度取决于符号间记忆的相关性以及符号概率分布的非均匀性。

    二:定长无失真信源编码定理

    1:典型序列性质的数学表达。

    l:是信源符号的平均码长
    2:定长码(所有码字的码长相同) 

     3:定长信源编码定理(考虑N次扩展信源)

     注意:H(S)和logr的底数必须相同。且:无失真编码是使得误码率足够小而不是必须为0;想实现无失真编码,扩展次数要足够大。

    三:变长无失真信源编码 

    又叫:香农第一定理,它给出了平均码长的压缩下限,与信源的熵有关。

     H_{r}(S):是编码信源符号所需的平均码长的下界。

    四:几种码

    1:非奇异码

     2:唯一可译码(不存在译码的二义性)

    3:即时码

    习题:会识别变长码,定长码,奇异码和扩展信源 

    定长码:码一   变长码:码二码三     奇异码:码三(11可以表示两个符号)
    所谓2次扩展就是:N*N.自己和自己,自己和别人的连接

    几种码的关系 

    非奇异码是保证无失真的前提,唯一可译码是保证译码唯一的前提,即时码是性质很好的一类码,读到便可直接译出。

    五:前缀码约束条件

    前缀码:可以用码树去表示,而且选用的符号(又叫:码本)没有字树,只能作为叶子。

    kraft不等式

    设符号表中的原始符号为:S={s_{1},s_{2},..,s_{n}},在大小为D进制的字符集上编码为前缀码的码字长度为:l_{1},l_{2},...,l_{n},则满足:反之, 若码长约束满足上述不等式  , 则必存在一组前缀码符合相应的码字长度。
    给出了:前缀码(即时码)的充要条件

    平均码长界限定理
    TH:对任意随机变量X进行D-进制前缀码编码,得到的码长:L\geq H_{D}(X)(平均码长不会小于熵)
    最优码长L^{*}满足:H_{D}(X)\leq L^{*}\leq H_{D}(X)+1

    注:H_{D}(X)=H(S)/logr 
    定理说明:为降低平均码长,大概率的符号要用较短的码字表示,小概率符号用较长的码字符号

    习题:

    展开全文
  • 以一幅灰度图像为例对通信系统的通信过程进行仿真,过程如下图所示: 1、不经过信道编码与译码,图像经过BSC信道传输后的误码率,此处的编码方法为霍夫曼编码。MATLAB仿真程序如下: clear all clc I0=imread...

    以一幅灰度图像为例对通信系统的通信过程进行仿真,过程如下图所示:
    图1 通信过程
    1、不经过信道编码与译码,图像经过BSC信道传输后的误码率,此处的编码方法为霍夫曼编码。MATLAB仿真程序如下:

    clear all
    clc
    I0=imread('Penguinshead3.jpg');
    I1=rgb2gray(I0);
    subplot(1,3,1),imshow(I0),title('原图')
    subplot(1,3,2),imshow(I1),title('灰度图')
    [m,n]=size(I1);
    I=reshape(I1,m*n,1);
    P_value=zeros(1,256);
    %---------------------------------------概率;
     for i=0:255
         P_value(i+1)=length(find(I==i))/(m*n);  %各像素值概率
     end
    f=numel(I);                                      %频数
    P_symbol=zeros(m*n,1);
    for i=1:m
        for j=1:n
            P_symbol(i,j)=length(find(I==unique(i)))/f;%各信源符号概率矩阵
        end
    end 
    %--------------------------------霍夫曼编码
    k=0:255;
    dict=huffmandict(k,P_value);           %生成编码字典
    huffmancode=cell(length(I),2);         %元胞数组存放对应编码
    for i=1:m*n
        huffmancode{i,1}=I(i);
    end
    for i=1:length(I)
        for j=1:256
            if huffmancode{i,1}==dict{j,1}
                huffmancode{i,2}=dict{j,2};
            end
        end
    end
    %----------------------------通过BSC信道
    bsc_code=huffmancode;        %通过bsc信道后的编码
    for i=1:length(I)
        bsc_code{i,2}=bsc(huffmancode{i,2},0.001);
    end
    % --------------------------------译码
    bsccode=bsc_code{1,2};
    for i=2:length(I)
        bsccode0=bsc_code{i,2};
        L=length(bsccode0);
        bsccode(end+1:end+L)=bsccode0;       %转换为一串字符
    end
    deco=huffmandeco(bsccode',dict);         %译码
    %----------------------------------------译码后存在错误
    rdeco=zeros(length(I),1);                      %错误处理
    L=length(I)-length(deco);
    if L<=0
        rdeco=deco(1:end-abs(L));                  %截断
    else
        a=ones(abs(L),1);                          %补足   
        rdeco(1:length(deco))=deco;
        rdeco(length(deco)+1:end)=195*a;  
    end
    Ideco=reshape(rdeco,m,n);
    subplot(1,3,3),imshow(uint8(Ideco));title('经BSC信道传输后的图像');
    error=length(find(Ideco~=I1));
    fprintf('误码率:%.4f\n',error/length(I));
    

    传输结果如下图所示:
    图2 无信道译码与编码
    上图表示的是仅经信源编码与译码,新宿的得到的结果。可以看到图像存在失真,此时的误码率为:
    在这里插入图片描述
    2、经过信道译码,此处的信道编码采用汉明码。MATLAB仿真程序如下:

    clear all
    clc
    I0=imread('Penguinshead3.jpg');
    subplot(1,3,1),imshow(I0),title('原图')
    I1=rgb2gray(I0);
    subplot(1,3,2);imshow(I1);title('信源发出的消息');
    [m,n]=size(I1);
    I=I1(:);
    P=zeros(1,256);
    %---------------------------------------概率;
    for i=0:255
        P(i+1)=length(find(I==i))/(m*n);
    end
    %---------------------------------------编码译码
    k=0:255;
    dict=huffmandict(k,P);                    %生成霍夫曼码字典
    enco=huffmanenco(I,dict);                 %霍夫曼码信源编码
    code=encode(enco,15,11);                  %汉明码信道编码
    bsc_code=bsc(code,0.001);                 %通过BSC信道
    rcvcode=decode(bsc_code,15,11);           %汉明码信道译码
    deco=huffmandeco(enco,dict);              %霍夫曼码信源译码
    Ireco=reshape(deco,m,n);
    subplot(1,3,3);imshow(uint8(Ireco));title('信宿接收的消息');
    error=length(find(Ireco~=I1));            %误码数
    fprintf('误码率:%0.4f\n',error/length(I));
    

    经信道传输后的图像如下图所示:
    图3 经过信源信道编码与译码
    此时图像无失真,误码率为:
    在这里插入图片描述
    可以明显看到第二种方式的误码率远远小于第一种方式的误码率,由此可看出在通信过程中进行信道编码与译码的重要性。
    而方式1的误码率高的原因有以下三点:
    (1)传输图像较小,像素值少。图像越小,编码表的码字越少,经信道传输后,越容易出现非编码表码字。(2)对于编码表码字处理的译码译码方式简单,对于译码后的编码像素值采用舍弃译码后末尾的像素值与补足像素值(由于使用的图像右下角的像素值在195左右,因此对与译码后长度不足的像素值序列,补充像素值为195的像素)的方式存在较大的误差。(3)未经过信道编码与译码。
    必须说明的是由于上述第(2)点原因,在BSC信道的转移概率比较大的时候(p>0.1)时,方式1能够运行通过的概率很低,当信道的转移概率很小时,该方式的误码率也会比较小。

    展开全文
  • 信源编码的三种方式与实现

    万次阅读 多人点赞 2019-01-15 02:01:21
    信源编码的三种方式与实现一、本文概述二、编码原理1. 哈夫曼编码2. 算术编码3. LZ编码三、算法设计思路1. 哈夫曼编码a. 设置功能结构体和函数b. 压缩文件初始化统计表频度读入文件并统计频度对统计表频度排序建立...
  • 信源编码与信道编码

    万次阅读 多人点赞 2017-03-26 17:02:44
    信源编码和信道编码的发展历程 信源编码:  最原始的信院编码就是莫尔斯电码,另外还有ASCII码和电报码都是信源编码。但现代通信应用中常见的信源编码方式有:Huffman编码、算术编码、L-Z编码,这三种都是无损...
  • 该方案通过反馈检测到的重组信源的信息来改变译码过程中解码器间传递的外信息,从而提高信道译码的纠错能力。仿真结果表明,运用该方案至少可以减少一个数量级的比特错误,而且用较小的迭代次数就能达到较高迭代次数...
  • 第五章-信源编码(二)

    千次阅读 2016-10-21 22:02:48
    若将信源X通过二元信道传输,就必须把信源符号ai变换成由0,1符号组成的码符号序列,这个过程就是信源编码。 码可分为两类: 固定长度的码,码中所有码字的长度 都相同,如表5-1中的码1就是定长
  • 信息论基础(学习笔记整理)

    万次阅读 多人点赞 2019-06-08 13:24:12
    信源译码器 把经过信道译码器核对过的信息序列转换成适合接收者接收的信息形式。转换过程与信源编码方式相关。 通信的结果 通信的结果是消除或部分消除传递过程中的不确定性,从而获得准确的信息。 数学期望...
  • 限失真信源编码1

    2021-07-08 10:15:28
    实际信息处理过程,往往存在失真: ①连续信源编码必然存在失真(不可能从根本上去除量化误差) ②一定范围的失真可以大幅度提高编码效率。(降低信息率有利于传输和处理) ③无失真编码并不总是必须的。比如:...
  • 计算输入信源符号序列所对应的区间,然后在区间中任取一点,以其二进制表示适当截断作为序列的编码结果。 二、算术编码的原理 设输入信源序列为 初始时,区间长度为[0,1)。其由F (1)分为[0,????(1))和[????(1),1)两...
  • [实验]无失真信源压缩编码

    千次阅读 2018-03-19 20:09:04
    实验一 无失真信源压缩编码此文系后续整理,懒得copy,对应的方法可以根据需要可以直接下载代码,附件:...
  • 2、 观察了解PAM信号形成的过程 3、 了解混迭效应形成的原因 实验二 PCM编译码器系统 一、实验目的 1、 了解语音编码的工作原理,验证PCM编译码原理; 2、 熟悉PCM抽样时钟、编码数据和输入/输出时钟之间的关系...
  • 数学上,信源是产生随机变量XXX,随机矢量X和随机过程X(t)的源。 信源是发出消息(序列)的设备 离散单符号信源 离散多符号信源 当离散多符号信源为无记忆信源时: 离散无记忆信源的N次扩展信源 离散...
  • 在算术编码中,消息用0到1之间的实数进行编码。算术编码用到了两个基本的参数:符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率,也决定编码过程信源符号的间隔,而这些间隔包含在0到1之间
  • 其次,设计相应的译码器,并改进现有的联合译码算法,在译码中引入新的信息交互过程,提高了译码性能。仿真结果表明:该方案的性能优于现有的基于伴随式的分布式联合信源信道编码方案的性能,而且在信噪比较高时,该...
  • 本课题是实现信源编解码:PCM编码+ 数据压缩+信道(加性噪声)+数据解压缩+PCM译码。利用C语言使编码器实现输入信号完成PCM技术的三个过程:采样、量化与编码,解码器实现还原原信号过程。 二、设计目的 脉冲编码...
  • 稀疏网络编码译码概率的马尔可夫链模型 P. Garrido, D. E. Lucani and R. Agüero, “Markov Chain Model for the Decoding Probability of Sparse Network Coding,” in IEEE Transactions on Communications, vol....
  • 《计算机网络技术》第二章课后习题答案(全)

    万次阅读 多人点赞 2019-08-02 22:02:34
    接收设备:用于完成发送设备的反变换,即进行译码和解调,还原原始的发送信号。 信宿:是信号的终点,并将信号转换为人们能识别的消息。 5.简述单向通信、双向交替通信和双向同时通信的特点。并各举一种实际应用...
  • 信源编码的功能 压缩编码 模数转换 为什么要数字化? 数字通信的优越性;现实的模拟量 A/D转换(数字化编码)的技术:波形编码和参量编码 波形编码:抽样(时间离散化)、量化(幅度离散化)、编码(二进制) ...
  • 信源编码算法 •费诺编码 Fano coding •哈夫曼编码 Huffman coding   1.费诺编码   编码步骤 1.将信源符号按照其概率大小,从大到小排列; 2.将这一组信源符号分成概率之和尽可能接近或者相等的一组(即...
  • 用C语言实现哈弗曼编码与译码信源与编码译码结果保存到文件中
  • 信息论实验-唯一可译码判决准则

    千次阅读 2017-08-22 11:46:46
    掌握C语言字符串处理程序的设计和调试技术实验要求已知:信源符号个数r、码字集合C。 输入:任意的一个码。码字个数和每个具体的码字在运行时从键盘输入 输出:判决(是唯一可译码/不是唯一可译码)。实验原理A.A....
  • 信道编码译码(ECC)学习笔记

    千次阅读 2020-09-24 00:12:37
    信源即为发出信号的源头,信宿是接收信号的物体也就是信号的归宿,信道即为信源发出的信号到信宿接收到的中间过程经历的“路途”,信号的通道。由于真实世界中并不存在理想信道,故而就需要“ECC”出场啦! 纠错能力...
  • 信道编码技术通过在发送信息序列上增加额外的校验比特,并在接收端采用译码技术对传输过程中产生的差错进行纠正,从而实现发送信息序列的正确接收。 半个多世纪来,研究人员提出了多种纠错码技术(RS码、卷积码、...
  • OFDM之Viterbi译码器原理

    千次阅读 2015-09-09 16:43:00
    Viterbi译码
  • 算法流程图 代码 题目要求:设信源可能输出的符号是26个字母,且每个字母出现的概率未知,试编写程序可以对任意字母序列(如presentation)进行自适应模式的算术编码,并进行相应的译码。(采用 8个字符一组,用...
  • 信源编码的代码实现 (c++版)
  • 数字通信系统实际信道中,存在着各种对传输信息产生不同程度影响的噪声和干扰,这就使信息从信源传送给信宿的过程中,不可避免地发生错误,使发送的码字与信道传输后所接收的码字之间存在差异,称这种差异为差错。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 847
精华内容 338
关键字:

信源译码过程