二进制译码器

二进制译码器（精选四篇）

二进制译码器 篇1

●纸牌解码器

先从一个纸牌游戏开始,取扑克牌若干,正面朝上代表数码1,背面朝上代表数码0,如果将要解码的二进制数字是“10”,则将扑克牌以正面朝上和背面朝上两两搭配为一组,并将这个模式重复四次,也就是“正反正反正反正反”八张牌。然后背诵“咒语”——翻翻翻留留翻留留,其中“翻”代表把牌翻个面,“留”代表不翻面。前两张牌称为第零组,次两张牌称为第一组,再次两张为第二组,最后两张为第三组。翻牌前初始状态如图1所示。

根据“咒语”翻面后,就成了图2所示的状态。

可以看出,第零组是一背一正,第一组全是背面,第二组全是正面,第三组是一正一背。全是正面的那一组是第二组,而二进制数“10”所对应的十进制数恰好就是2。

再举一个例子,二进制数“11”可用两张朝上的牌来代表,先将这个模式重复四次(如图3)。

然后根据“翻翻翻留留翻留留”的“咒语”翻牌,得到图4所示的状态。

可见解码后的数字是3,因为只有第三组两张都是正面。其余的情况,大家可以自己试一下。

●纸板解码器

根据以上原理再进一步,可以设计出更精巧的纸板解码器(如上页图5)。

按图样剪两张纸板,两边伸出两个“小耳朵”,“小耳朵”一面写“0”,翻过来另一面写“1”。另外,再剪一张矩形纸板作为底板,标上“0”“1”“2”“3”四个十进制数字作为输出。然后将有“小耳朵”的两张纸板叠在底板上,露出的缺口恰好可以显示一个十进制数(如上页图6)。

两张都是正面,叠在一起则表示输入为“00”,输出为“0”。上页图7分别是“01”得“1”、“10”得“2”和“11”得“3”的情况。

这样,纸板解码器便大功告成,虽然制作简单,但有明确的输入端和输出端,而且还仿佛具有自动运算的功能。

做一个二进制解码器（续） 篇2

画图软件中的图画解码器

先来试试画图软件，没错，就是Windows系统自带的画图软件，它不仅可以用来画“解码器”，在一定程度上也可以模拟“解码器”的运行。在画图软件中，用非常浅的颜色画出图1（注意：线条和阿拉伯数字之间的空隙是有意留出的）。如图1所示，有四个矩形方框作为输入装置，有四个较大的数字作为输出装置。那么这个系统是怎样实现二进制解码的呢？

这里需要用到的工具是图标为 的填充工具，选择一种比较深的颜色，然后用填充工具点击作为输入装置的矩形（如图2左）。图2右是真实运行后得到的效果。

点击“0”和“0”之后，“神奇”的事情发生了，只有数码“0”能完整、清晰地显现出来。其他数码要么残缺不全，要么干脆不显示。

如果点击的是“1”和“0”，显示出来的就是“2”（如图3），以此类推。实际上，画图软件并不会真的进行逻辑运算，这个实验利用排列组合的原理，将二进制数相对应的十进制数码填满颜色。

逻辑门解码器

如果明白了上面图画解码器的原理，那么，逻辑门解码器的工作原理，就更容易弄明白了。

可以用Logisim软件来模拟二进制解码的过程。如图4所示，当输入“1”和“1”后，3号灯被点亮。可以看出，电路通过两个非门和四个与门，来实现“非与非”“非与不非”“不非与非”“不非与不非”这四种排列组合。

做一个二进制解码器(续) 篇3

●画图软件中的图画解码器

先来试试画图软件,没错,就是Windows系统自带的画图软件,它不仅可以用来画“解码器”,在一定程度上也可以模拟“解码器”的运行。在画图软件中,用非常浅的颜色画出图1(注意:线条和阿拉伯数字之间的空隙是有意留出的)。如图1所示,有四个矩形方框作为输入装置,有四个较大的数字作为输出装置。那么这个系统是怎样实现二进制解码的呢?

点击“0”和“0”之后,“神奇”的事情发生了,只有数码“0”能完整、清晰地显现出来。其他数码要么残缺不全,要么干脆不显示。

如果点击的是“1”和“0”,显示出来的就是“2”(如图3),以此类推。实际上,画图软件并不会真的进行逻辑运算,这个实验利用排列组合的原理,将二进制数相对应的十进制数码填满颜色。

●逻辑门解码器

如果明白了上面图画解码器的原理,那么,逻辑门解码器的工作原理,就更容易弄明白了。

可以用Logisim软件来模拟二进制解码的过程。如图4所示,当输入“1”和“1”后,3号灯被点亮。可以看出,电路通过两个非门和四个与门,来实现“非与非”“非与不非”“不非与非”“不非与不非”这四种排列组合。

一种多进制喷泉码短码的编译码方法 篇4

数字喷泉码是一种应用于删除信道的纠错编码技术, 其典型应用多媒体广播多播、分布式存储、容迟容断网络等[1]。该编码的基本思想如下:在发送端, 将需要发送的K个数据包进行线性组合, 按需生成N个编码包;在接收端, 接收到K个编码包, 求解线性方程组就可以求出信源数据包。每一个传输的编码包可嵌入包编号、CRC校验等。接收端检查CRC即可获知某编码包是否被正确传输, 因而信道可等效为删除信道。采用伪随机的方法选取编码系数, 接收端根据包编号即可生成编码系数, 恢复编码方程, 因而无须传输编码系数。基于此, 不管接收到哪些编码包, 无论喷泉包的顺序如何, 接收端都可以求解线性方程组恢复原始数据。这好比人们使用杯子接水来喝, 饮水者只关心杯子是否装满;至于哪些水滴接入杯中, 则不必关心。

基于喷泉码的基本思想, M.Luby和A.Shokrollahi分别提出了两种实用的喷泉码, 即LT码和Raptor码。目前, LT码已经在无线组播、分布式存储等多个领域得到应用[2,3,4,5]。但目前实用的喷泉码在码长很长时, 其译码复杂度、译码性能和编码效率表现优异。但对于短喷泉码, 这些性能表现不佳。例如, 采用LT码, 如果希望编码开销小于5%, 则信源长度需要10000以上。如果编码长度小于1000, 则编码开销高于30%。实际的有线通信、无线通信及文件存储系统, 长度很短的信息、短文件比较多;这些短信息、短文件不太适合码长很长的喷泉码编码。基于此, 本文介绍一种高效率的多进制喷泉码。这种编码基于有限域, 其效率与二进制编码相比, 在效率和性能方面得到显著提升, 但译码复杂度仅略有上升。

2多进制喷泉码的编码

考虑二进制编码的线性方程组的系数矩阵只能选取0和1, 因此希望矩阵的秩为K, 比较有效的方法是增加方程组的数量N。这样, 当码长较短时, 增加N会造成编码效率的下降。如果采用多进制编码, 由于系数矩阵中每个元素的维度增加, 容易达到满秩。基于此, 采用多进制编码可有效提高短码的编码效率。

设v∞=[v1, v2, ······]表示喷泉码编码序列, 其中vi (i=1, 2, ) 表示第i个编码符号。令m=[m1, m2, , mK]T为信源矢量, 其长度为K。设信源和编码序列的元素取自于有限域GF (q) 。编码矢量中非零元素的个数称为该矢量的重量。

对喷泉码进行编码的方法如下:

选取非负整数di。一般地, 该非负整数可基于鲁棒孤子分布µ (d) 随机选取。称di为编码符号Vi的编码度。然后, 随机均匀地从K个信源符号中选di个符号, 并基于有限域GF (q) 随机均匀地生成di个非零编码系数。将选出的信源符号和这些非零系数对应相乘, 然后作和, 就得到编码符号Vi的值。

3多进制喷泉码的译码算法

由上小节可知, 多进制喷泉编码可表示成线性方程组w=A·m。只要矩阵A的秩为K, 收到w=[w1, w2, …, wN]T后, 译码器通过基于有限域GF (q) 的高斯消元就能够求解出信源矢量m=[m1, m2, …, wK]T, 实现最大似然序列译码。但直接进行高斯消元时, 由于存在大量的行列置换及消元所需的乘法和加法运算, 复杂度为O (K2) 到O (K3) , 难以实际应用。事实上, 注意到的w=A·m矩阵为稀疏矩阵。利用该特性, 可大大降低译码复杂度。基于此, 给出低复杂度译码过程如下:

(1) 对矩阵A进行主元选择。

主元选择的步骤和常规的高斯消元法一致, 包括K步前向迭代过程。在第K步, 将第K行用 (K, K) 位置的元素归一化, 然后将该行的适当倍数并叠加到下面各行, 使下面各行第K列的元素全化成零。重复该过程K次, 矩阵变成上三角形式。为了最小化局部填充元和局部操作量, 选取最大填入和操作数最小的元素作为主元。

(2) 主元原位高斯消元。

在常规的高斯消元法中, 存在大量的行交换。由于行交换需要反复复制数据, 造成译码计算和存储量的上升。对于稀疏编码矩阵, 矩阵中存在大量的零元, 这些零元参加运算和存储器的存取会造成存储和计算资源的浪费。实际上, 不需要进行实际的行列交换, 用2K个存储单元记录迭代过程中主元行号和列号就可以了。

具体地, 在迭代过程的每一步, 基于稀疏存储, 每次消元, 根据所存取的行, 读取非零元素, 然后进行消元操作, 更新非零元素的存储记录。在此基础上, 根据步骤1选取主元, 记录其行号和列号。重复该过程, 直到完成整个方程组的消元, 将系数矩阵化为下三角矩阵。

最后, 采用后向迭代, 求解线性方程组w=A·m中的未知量m的元素, 得到译码输出序列m。这样就完成了多进制喷泉码的编码和译码过程。

4仿真结果

为了说明使用鲁棒孤子分布选取编码度时多进制喷泉码的性能, 选取喷泉短码长度K=100, C=0.05, 改变参数δ, 编码度采用鲁棒孤子分布, 使用多进制喷泉码编译码方法。选取q=2和q=16两种情况。经验证, 在译码失败概率为10-2时, 码长为100的16进制短码, 其编码开销只需要5%。对于二进制编码, 若实现这样低的编码开销, 如第1节所述, 其编码长度需要10000以上。

使用鲁棒孤子分布, 选取N=1250, K=1000, C=0.05, δ=0.05构造二进制和十六进制的LT码, 基于稀疏矩阵的高斯消元法实现了最大似然序列译码。经仿真验证, 多进制喷泉码的最大似然译码远远快于常规的高斯消元法, 计算复杂度仅为BP算法的4倍。作为比较, 通过仿真验证常规的高斯消元法对该编码译码的复杂度, 发现采用常规高斯消元法时, 计算复杂度为BP算法的170倍, 不具实用价值。这说明, 多进制喷泉码比二进制编码在复杂度方面只略有提高, 但短码性能获得显著提升。

5结语

二进制喷泉码在码长很长时具有很高的效率和优异的译码性能。但码长较短时, 编码效率急剧下降。基于此, 本文介绍了一种多进制喷泉码, 给出了喷泉短码的编码, 并利用编码矩阵的稀疏特性, 讨论了主元原位消元和稀疏存储和计算的低复杂度译码方法。经仿真验证, 与二进制编码相比, 多进制编码在效率和性能方面得到显著提升, 但译码复杂度仅略有上升。

参考文献

[1]LUBY M.CODES LT.In Proceeding of the 43rd Annual IEEE Symposium[J].Foundations of Computer Science, 2002 (10) :271-282.

[2]Mitzenmacher M.Digital Fountains:A Survey and Look Forward[J].Information Theory Workshop, 2004 (10) :271-276.

[3]LUBY M.CODES LT.[J].In Proceeding of the 43rd Annual Symposium[J].Foundations of Computer Science, 2002 (6) :271-282.

[4]PALANKI R, Yedidia J S.Rateless codes on Noisy Channels[J].International Symposium on Information Theory, 2004 (6) :1008-1010.