汉明距离
在信息论中，两个等长字符串之间的汉明距离（）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。 汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。 範例 例如： 1011101与1001001之间的汉明距离是2。 2143896与2233796之间的汉明距离是3。 "tone…
标签：#编码理论
共 30 篇文章
低密度奇偶檢查碼
低密度奇偶檢查碼（Low-density parity-check code，LDPC code），是線性分組碼（linear block code）的一種，用於更正傳輸過程中發生錯誤的編碼方式。 歷史 在1962年，低密度奇偶檢查碼(LDPC code)即被羅伯特·加拉格提出，並被證明其錯誤校正能力非常接近理論最大值，香農極限。但受限於當時技術，低密度奇偶檢查碼並無法實作。近年，低密度奇偶檢查碼被重新發現，並隨著積體電路的技術演進，低…
信道编码
在计算机科学领域，信道编码（channel code）被广泛用作表示编码错误监测和纠正的术语，有时候也可以在通信和存储领域用作表示数字调制方式。信道编码用来在数据传输的时候保护数据，还可以在出现错误的时候来恢复数据。 设计和分析信道编码的原理叫做噪音信道编码定理。 参见 信道容量 噪音信道编码定理 * 错误监测和纠正
网络编码
网络编码是一种通过中继节点对接收到的信息进行编码来达到提高多播网络容量的技术。Rudolf Ahlswede, Ning Cai, Shuo-Yen Robert Li, Raymond W. Yeung在2000年首次提出网络编码的概念。 在右图的网络拓扑中，s节点试图向t_{1}, t_{2}组播两条消息x,y。设每条消息占用的带宽为1，每个节点之间的网络带宽也为1，那么每个节点之间只能同时传输一条消息。线路cd上会需要同时传输x,…
喷泉码
在编码理论中，喷泉码（也称为无码率抹除码）是一类抹除码，这种编码能够从一组给定的源符号序列中产生一串不限长度的编码符号序列，在理想情况下，从编码符号序列中获得大小和源符号相同或稍大的任意子集，便可恢复源符号。术语“喷泉”或“无码率”是指此类编码不表现出固定的编码率。 最优的喷泉码应当能够从任意k个编码符号中恢复出k个源符号。喷泉码被认为具有高效的编解码算法，能以高概率从任意k’个编码符号恢复k个源符号（k’仅稍大于k）。 LT码是第一种…
分布式信源编码
分布式信源编码（Distributed Source Coding，DSC）是对信息互相关联但不互相通信的信源的一种信息压缩方式. 它和其他信源编码不同的是，在这里使用的是信道码。 分布式信源编码的主要应用领域有传感器网络（sensor network）和图像，视频，多媒体压缩). 其最主要的特点有两条，第一，编码计算非常简单，解码相对比较复杂;第二，互不通信的信息相关的信源压缩可以达到有互相通信的压缩效率。 理论值 做为信息论的一个分…
克拉夫特不等式
在编码理论，克拉夫特不等式给出了一个码字长度集合存在唯一可解编码/单义可译码（uniquely decodable code）的必要条件。因为这个不等式在前缀码和树上面应用很多，所以在计算机科学和信息学中很常用。 克拉夫特不等式对码字限制长度以保证前缀编码的可能性。这个不等式说明码字长度指数的倒数的分布和概率质量函数很相似。克拉夫特不等式can be thought of in terms of a constrained budget…
孤子分布
孤子分布是一种出现于抹除码理论中的离散概率分布。卢比的论文提出了两种形式的分布，分别是理想孤子分布和鲁棒孤子分布。 理想分布 理想孤子分布是在整数上的概率分布，从1至N，其中N是分布中的唯一参数。概率质量函数由下式给出： : p(1)= \frac{1}{N}, : p(k)= \frac{1}{k(k-1)} \qquad (k=2,3,\dots,N). \, 鲁棒分布 该分布的鲁棒形式为向理想孤子分布质量函数的元素中添加一组额外的…
低密度同位元檢查累積碼
低密度同位元檢查累積碼由低密度奇偶檢查碼low-density parity-check (LDPC)和一個累加器組成。 其運作方式為Bit Node以二位元模組的方式相加到Check Nodes,根據tanner graph。 然後，Check nodes的值以modulo-two被累加。 利用這種方式，通道解碼端的解碼器可以避免有一個check node沒有被連結到任何bit node的狀況。 經過累加後，累加的位元會被存在一個緩衝…
非累贅取樣編碼
非累贅取樣編碼法 以下將探討兩類非累贅取樣編碼法：多項式預測器及多項式內插法 多項式預測器所採取的方法是：測試下一個取樣看看他是不是落在一個n次多項市所展開的範圍內。最常被使用的是0次及1次多項式。著名的串長編碼(run-length coding)則是0次多項式的一個特別版本。 多項式內插法與多項式預測器類似，唯一的不同是他允許的機動的改變其所展開的範圍。一次多項式內插法，又名善行演算法，是用許多線段來取代原波形。 多項式預測器 非累…