但什么是汉明码?纠错码的起源
But what are Hamming codes? The origin of error correction
频道:3Blue1Brown · 时长:20:05 · 发布:2020-09-04 · 播放:3073710
简介
3Blue1Brown 以探索方式介绍纠错码,从定位翻转比特的谜题出发构建汉明码。它解释了奇偶校验的思想及其为何如此高效。
HN 为什么推荐
HN 推荐它作为对汉明码极有价值、直观易懂的解释,与面向硬件的讲解相得益彰。
我强烈推荐任何对这个话题感兴趣的人去看看这些视频中的任何一个 — HN, 2022
中文字幕节选
你有没有想过,为什么CD 或DVD被划伤后,仍然能播放出它存储的内容? 划痕确实会影响光盘上的1和0, 所以读出的数据与存储的数据不同, 但除非划痕非常严重,否则读出的比特会被解码 成与编码时完全相同的文件,一个比特一个比特的副本, 尽管有所有这些错误。 有一大堆数学上的巧妙方法让我们能够存储数据, 同样重要的是传输数据,以某种能抵抗错误的方式。 好吧,实际上并不需要那么多 聪明才智就能想出做到这一点的方法。 任何文件,无论是视频、声音、文本、代码, 图像,等等,最终都是1和0的序列。 一个简单的策略来纠正任何被翻转的比特 就是存储每个比特的三份副本。 然后读取这个文件的机器可以比较这三份副本, 每当出现差异时,总是取三份中的最佳两份。 但这意味着用三分之二的空间来做冗余。 即使如此,放弃了那么多空间, 对于超过一个比特被翻转的情况,也没有强有力的保证。 更有趣的问题是,如何做到 在纠正错误的同时,尽可能少地牺牲空间。 例如,使用你将在本视频中学到的方法, 你可以将数据存储在256比特的块中,每个块使用9个比特,9个! 作为某种冗余,而其他247个比特可以自由携带任何 有意义的讯息或数据。 而且仍然会是这样的情况:如果这里任何一个比特被翻转, 仅通过查看这个块,而不需要其他信息, 机器就能够识别出存在错误,并精确地知道 错误在哪里,从而知道如何纠正它。 老实说,这感觉就像魔法。 对于这个特定的方案,如果两个比特被翻转, 机器至少能够检测到有两个错误, 尽管它不知道如何修复它们。 我们稍后会稍微讨论一下,对于不同大小的块,这是如何扩展的。 让你能够像这样纠正错误的方法, 很合理地,被称为纠错码。 在上个世纪的大部分时间里,这个领域一直是真正丰富的来源, 提供了令人惊讶的深奥数学,被融入我们每天使用的设备中。 这里的目标是让你非常透彻地理解 最早的例子之一,称为汉明码。 顺便说一下,我构思这个视频结构的方式,与其说是 尽可能直接地解释,不如说是促使 你自己发明它,偶尔给予一些温和的引导。 所以当你觉得你看到它的发展方向时, 在某个时刻,花点时间暂停一下, 在我告诉你之前,主动预测这个方案会是什么。 另外,如果你想让你的理解深入到硬件层面, Ben Eater制作了一个与本视频配套的视频,向你展示如何 在面包板上实际实现汉明码,这非常令人满足。 你应该知道,汉明码不像更现代的编码那样广泛使用, 比如里德-所罗门算法,但有一种特定的魔力在于 这个任务一开始感觉多么不可能, 而一旦你了解了汉明码,它又显得多么完全合理。 纠错的基本原理是 在所有可能讯息的广阔空间中, 只有一部分子集会被认为是有效讯息。 打个比方,想想拼写正确的单词和拼写错误的单词。 每当一个有效讯息被改变,接收方负责 将他们看到的内容纠正到最近的有效邻居,就像你处理拼写错误一样。 然而,要想出一个具体的算法来高效地对这类消息进行分类,
HN 上的讨论
要理解纠错的工作原理并了解更多关于汉明码和里德-所罗门码的知识,3Blue1Brown和Ben Eater是无价的。3Blue1Brown和Ben Eater分别是数学和计算机工程领域最优秀的教育内容创作者之一。我强烈推荐任何对该主题感兴趣的人查看这些视频:如何发送自校正消息(汉明码):[VIDEO] 汉明码第二部分,一切的优雅:[LINK] 以及Ben Eater关于纠错的五个视频中的任何一个:[LINK] 顺便说一句,Ben Eater的所有视频和演示都是使用他在面包板上逐步构建的8位计算机完成的。非常令人印象深刻和鼓舞人心。 — Hanschri, 2022-11
如果你想从数学角度了解更多关于汉明码的知识,我推荐3Blue1Brown的YouTube系列:> 如何发送自校正消息(汉明码) - [VIDEO] > 汉明码第二部分,一切的优雅 - [LINK] 与Ben Eater的视频相关,如果你想要关于低级计算机硬件的视角:> 什么是纠错?硬件中的汉明码 - [LINK] — WaffleIronMaker, 2023-08
我非常喜欢Reducible关于霍夫曼编码的这个视频:[LINK],以及3Blue1Brown关于汉明码的视频:[VIDEO] — adamisntdead, 2021-09
不错!与3Blue1Brown关于该主题的视频搭配得很好:[VIDEO] 汉明的书《做科学与工程的艺术》是一本扎实的读物。主题混杂,围绕解决问题的技巧和陷阱展开。 — the__alchemist, 2020-09
相关视频
- 用 Shor 算法以量子速度进行黑客攻击 | Infinite Series · PBS Infinite Series · 16:36
- 量子计算机的数学原理 | Infinite Series · PBS Infinite Series · 12:35
- 将1930年的电传打字机用作Linux终端 · CuriousMarc · 16:33
- 代码的艺术 - Dylan Beattie · NDC Conferences · 1:00:48
- Line Goes Up – NFT 的问题 · Folding Ideas · 2:18:23
- 演讲:电子游戏与教育的未来 · Jonathan Blow · 2:44:28
- 最快的登机方式感觉像最慢的 · CGP Grey · 8:27
- 向量 | 第1章,线性代数的本质 · 3Blue1Brown · 9:51
- 但什么是傅里叶变换?视觉介绍。 · 3Blue1Brown · 19:41
- 但什么是神经网络?| 深度学习第一章 · 3Blue1Brown · 18:40
- 贝塞尔曲线之美 · Freya Holmér · 24:25
- D/A 与 A/D | 数字展示与讲解(Monty Montgomery @ xiph.org) · FL Studio · 23:52
- 样条曲线的连续性 · Freya Holmér · 1:13:50
- Jim Simons(完整版访谈)- Numberphile · Numberphile2 · 1:00:43
- 但比特币究竟是如何运作的? · 3Blue1Brown · 25:15
- APL中的康威生命游戏 · Dyalog · 7:47