量子纠错
量子纠错（，QEC）是量子计算领域应用的一套关键技术，旨在保护量子信息免受退相干及其他量子噪声源所引发错误的影响。理论上，量子纠错对于实现容错量子计算至关重要，它能够有效降低噪声对已存储量子信息、量子逻辑门操作、量子态制备及量子测量的负面效应。通过实施有效的量子纠错，即使构建量子计算机的物理量子比特保真度相对较低，也能执行具有更高复杂度或更大线路深度的量子算法。 经典的纠错技术通常利用冗余（redundancy）原理。其中，最简单（但效…
标签：#编码理论
共 30 篇文章
可变长度编码
编码理论中的可变长度编码（）指将源“符号”映射到可变位元的编码。计算机科学中的等效概念是位串。 可变长度编码允许源信息被以零误（无损数据压缩）的结果完成压缩和解压缩，且仍可读取每个符号。通过妥善的编码策略，能将独立同分布的源信息压缩到几乎任意接近其熵的程度。而固定长度编码方法只能对大数据块进行数据压缩，且任何超过可能性总数的对数的压缩都存在有限的失败概率，尽管这可能任意小。 知名的可变长度编码策略包括霍夫曼编码、Lempel-Ziv编码…
盧比變換碼
盧比變換碼（LT碼，英文：Luby transform codes, LT codes）是第一個最接近完善的抹除碼（erasure correcting codes）的實用湧泉碼（fountain codes），由 在1998年發明並於2002年發表。LT碼一個顯著的特徵是採用簡單且基礎的異或（XOR，\oplus）來編碼（encode）以及解碼（decode）。 LT碼的另一個特徵是它rateless，由於它可以產生無限量的訊息封包，…
李距离
李距离（Lee distance）是编码理论裡的一種距离函數。两个使用包含 q 個字母的字母表 {0, 1, …, q − 1}（q ≥ 2）且长度为 n 的字符串x_1 x_2 \dotsb x_n和y_1 y_2 \dotsb y_n之间的李氏距离被定义为 : \sum_{i=1}^n min(|x_i-y_i|,q-|x_i-y_i|) 当q=2或者q=3，李距离等价于汉明距离。 由李距离所长产生的度量空间是一个类似于离散的椭圆几…
线性码
编码理论中，线性码是一种纠错码，满足其任何码字的线性组合也是其码字。传统上，线性码分为分组码和卷积码两大类，尽管涡轮码可以看作是这两种类型的混合。 线性码的编码和解码可以有比其他码更有效的算法（参见伴随式解码）。 线性码用于前馈纠错，用于在通信信道上传输符号（例如，比特），以使在通信中出现错误时，消息块的接收者可以纠正或检测到一些错误。线性分组码的码字是一种符号块，这种符号块使用比要发送的原始值更多的符号进行编码。长度为n的线性码传输包…
霍夫曼编码
霍夫曼編碼（），又譯為哈夫曼编码、赫夫曼编码，是一種用於无损数据压缩的熵編碼（權編碼）演算法。由美國計算機科學家大衛·霍夫曼於1952年發明。 簡介 在计算机资讯处理中，霍夫曼編碼使用變長編碼表對源符號（如文件中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字符串的平均長度、期望值降低，從而達到無損壓縮數據的目的。 例如，…
萊文斯坦距離
莱文斯坦距离（）是编辑距离的一种。指两个字串之間，由一个转成另一个所需的最少编辑操作次数。 允许的编辑操作包括： 将一个字符替换成另一个字符 插入一个字符 刪除一个字符 俄羅斯科學家弗拉基米尔·莱文斯坦在1965年提出這個概念。 定义 如果分别用 |a| 和 |b| 表示 a, b 两个字符串的长度，那么它们的列文斯坦距离为 \operatorname{lev}_{a,b}(|a|,|b|)，它符合： :\qquad\operatorn…
汉明码
在電信領域中，漢明碼（），也称为海明码，是推广得到的一種线性纠错码，由理查德·衛斯里·漢明于1950年發明。相比而言，簡單的奇偶檢驗碼除了不能糾正錯誤之外，也只能偵測出奇數個的錯誤。汉明码是，它在于它分组长度相同、最小距离为3的码中能达到最高的码率。 用數學术语来说，漢明碼是一種二元線性碼。對於所有整數 ，存在一个分组长度 、 编码。因此汉明码的码率为 ，对于最小距离为3、分组长度为 的码来说是最高的。漢明碼的奇偶檢驗矩陣的是通過列出所…
编码理论
是一种广泛使用数据压缩以补偿阅读速度缓慢的编码。]] 编码理论（）是研究编码的性质以及它们在具体应用中的性能的理论。编码用于数据压缩、加密、，最近也用于网络编码中。不同学科（如信息论、電機工程學、数学、语言学以及计算机科学）都研究编码是为了设计出高效、可靠的数据传输方法。这通常需要去除冗余并校正（或检测）数据传输中的错误。 编码共分四类： 数据压缩（或信源编码） 前向錯誤更正（或信道编码） 加密编码 线路码 数据压缩和前向錯誤更正可以。…
汉明权重
汉明权重是一串符号中非零符号的个数。因此它等同于同样长度的全零符号串的汉明距离。在最为常见的数据位符号串中，它是1的个数。 历史及应用 汉明权重是以理查德·衛斯里·漢明的名字命名的，它在包括信息论、编码理论、密码学等多个领域都有应用。 高效实现 在密码学以及其它应用中经常需要计算数据位中1的个数，针对如何高效地实现人们已经广泛地进行了研究。一些处理器使用单个的命令进行计算，另外一些根据数据位向量使用并行运算进行处理。对于没有这些特性的处…
译码方法
在编码理论中，译码（）是将接收到的消息译成给定码元的的过程。有许多常用的将消息映射到码字的方法。这些方法通常用于在有噪信道（如）传输后恢复消息。 记号 C \subset \mathbb{F}_2^n 是指长度为 n 的；x,y 为 \mathbb{F}_2^n 的元素；而 d(x,y) 为它们之间的距离。 理想观察者译码 给定信号 x \in \mathbb{F}_2^n，则理想观察者译码会生成码字 y \in C。该过程得到这个解：…
置信度传播
置信度传播（），又称为乘积和信息传递（），是在贝叶斯网络、马尔可夫随机场等概率图模型中用于推断的一种信息传递算法。在给定已观测节点时，可以用该算法高效地计算未观测节点的边缘分布。置信度传播在人工智能、信息论中十分常见，已成功应用于低密度奇偶检查码、Turbo码、自由能估计、等不同领域。 置信度传播由美国计算机科学家朱迪亚·珀尔于1982年提出。最初该算法的运用范围仅限于树，不久则扩展到。此后，研究者发现在一般的图中该算法是一种十分有用的…
生成矩阵
在编码理论中，生成矩阵（）是一个矩阵，该矩阵的行是线性码的一组基。所有码字都是该矩阵的行的线性组合，也就是说，线性码是其生成矩阵的行空间。 术语 若 G 为一矩阵，它生成线性码 C 的的方式为， :w = s G, 其中 w 是线性码 C 的一个码字，而 s 是任意向量。 线性 [n, k, d]_q 码的生成矩阵的格式为 k \times n，其中 n 为码字的长度，k 为信息比特的数量（作为向量子空间的 C 的维数），d 为码的最小…
極化碼
極化碼（）是一種前向錯誤更正編碼方式，用於訊號傳輸。 構造的核心是通過信道極化（）處理，在編碼側採用方法使各個子信道呈現出不同的可靠性，當碼長持續增加時，部分信道將趨向於容量近於1的完美信道（無誤碼），另一部分信道趨向於容量接近於0的純噪聲信道，選擇在容量接近於1的信道上直接傳輸信息以逼近信道容量，是首个被证明能够达到香農極限的方法。 在解碼側，極化後的信道可用簡單的逐次干擾抵消解碼的方法，以較低的複雜度獲得與最大似然解碼相近的性能。 …
循环码
在编码理论中，循环码（）是一种分組碼，每个码字循环移位会得到同样属于该码的另一个码字。它们是拥有便于误差检测与校正的纠错码。 定义 令 \mathcal{C} 为有限域 GF(q) 上的分组长度为 n 的线性码。如果对于 C 中的每个 c=(c1,...,cn)，由循环移位得到的 GF(q)^n 中的字 (cn,c1,...,cn-1) 仍是一个码字，则 \mathcal{C} 称为循环码。由于向右循环移一位就相当于向左循环移 n − …
对偶码
在编码理论中，线性码的对偶码（） :C\subset\mathbb{F}_q^n 是有如下定义 :C^\perp = \{x \in \mathbb{F}_q^n \mid \langle x,c\rangle = 0\;\forall c \in C \} 的线性码，其中 :\langle x, c \rangle = \sum_{i=1}^n x_i c_i 是一个数量积。用线性代数的属于来说，对偶码是 C 对雙線性形式 的。 C …
多项式码
在编码理论中，多项式码（）是有效集合是由多項式（通常是固定长度的多项式）可以被特定多项式（长度较短，称为生成多项式）整除的一种线性码。 定义 对于有限域 GF(q)，其元素我们称作码元。为了建立多项式码，我们要确定一个 n 个码元的序列 a_{n-1}\ldots a_0 其多项式为 :a_{n-1}x^{n-1} + \cdots + a_1x + a_0.\, 对于整数 m \leq n，令 g(x) 为 m 阶多项式，称为生成多项…
前置碼
前置碼（），又譯前綴碼、前缀编码，是一種編碼系統。這種編碼系統通常是可变长度编码，在其中的每個碼字，都具備「前置性質」（prefix property），也就是說，在編碼中的每個碼字，都不能被其他碼字當成前置部位。舉例而言，編碼字 {9, 55} 具備了前置性質，但編碼字 {9, 5, 59, 55} 就不具備，因為其中的“5”是“59”及“55”的前置字。這也被稱為無首碼的代碼（，PFC，無前綴碼）。虽然哈夫曼编码只是派生的前缀码中众…
伯利坎普-韦尔奇算法
伯利坎普－韦尔奇算法（）是一種用於高效地解碼BCH碼與里德-所羅門碼的演算法，其名取自埃尔温·伯利坎普與勞埃德·韋爾奇。伯利坎普－韦尔奇算法的優點在於這一演算法僅需利用矩陣運算。這一演算法的時間複雜度為O(N^3)。 演算法 伯利坎普－韦尔奇算法通常被用於解碼里德-所羅門碼。假使在有限體GF(q)上有n個數字m_1, \dots , m_n，利用RS碼編為n-1次多項式P(i)=m_i。如果已知傳輸信道會錯誤傳輸k個值，那麼RS碼可以傳…
奇偶檢驗矩陣
在编码理论裡，線性區塊碼 C 的奇偶檢驗矩陣（）是描述的成分间必须满足的线性关系的一个矩阵。它可以用来决定一个特定向量是否为码字，也用在译码算法中。 定义 形式上，线性码 C 的奇偶檢驗矩陣 H 是对偶码 C⊥ 的生成矩阵。这就意味着当且仅当矩阵-向量乘积 （一些作者会写成其等价形式cH⊤ = 0）时，码字 c 才会在 C 中。 奇偶檢驗矩陣的行是奇偶检验方程的系数。也就是說，它們表示每个碼字中的某些數字（成分）如何線性組合可以等於零。…