Name: 漢明碼是什麼？差錯修正的起源！ (But what are Hamming codes? The origin of error correction)
Uploaded: 2026-01-07T04:47:41.000Z
Duration: 20 min 5 s

Have you ever wondered how it's possible to scratch a CD or a DVD and still have it play back whatever it's storing?

你有沒有想過，CD 或 DVD 刮傷了，裡面的東西還是能正常播放？

程度副詞

The scratch really does affect the ones and zeros on the disc, so it reads off different data from what was stored.

刮痕確實會影響光碟上的一和零，所以讀取的資料會跟原本儲存的不一樣。

情態副詞

But unless it's really scratched up, the bits that it reads off are decoded into precisely the same file that was encoded onto it, a bit for bit copy.

不過，除非颳得很嚴重，否則讀取的位元解碼後，會跟編碼上去的檔案一模一樣，是位元對位元的複製。

Despite all of those errors, there is a whole pile of mathematical cleverness that allows us to store data and just as importantly, to transmit data in a way that's resilient to errors.

儘管有這麼多錯誤，但有一大堆數學上的巧妙方法，讓我們能夠儲存資料，而且更重要的是，能夠以一種不容易出錯的方式傳輸資料。

Actually, it doesn't take that much cleverness to come up with a way to do this.

事實上，要找出方法來做到這點，並不需要太多的聰明才智。

Any file, whether it's a video or sound or text, some code, an image, whatever, is ultimately some sequence of ones and zeros.

任何檔案，不管是影片、聲音、文字、程式碼、圖片，任何東西，最終都是一連串的一和零。

And a simple strategy to correct any bit that gets flipped and would be to store three copies of each bit.

而一個簡單的策略來修正任何被翻轉的位元，就是儲存每個位元的三份副本。

Then the machine reading this file could compare these three copies and always take the best two out of three whenever there's a discrepancy.

然後讀取這個檔案的機器就可以比較這三份副本，只要有差異，就永遠取其中最好的兩份。

But what that means is using two thirds of your space for redundancy.

但這意味著要用三分之二的空間來做冗餘。

And even then, for all of that space given up, there's no strong guarantee about what happens if more than one bit gets flipped.

而且就算這樣，為了犧牲這麼多空間，如果有多個位元被翻轉，也無法強烈保證會發生什麼事。

The much more interesting question is how to make it so that errors can be corrected when, while giving up as little space as possible.

更有趣的問題是，如何在盡可能少浪費空間的情況下，讓錯誤可以被修正。

For example, using the method that you'll learn about this video, you could store your data in 256 bit blocks, where each block uses 9 bits, 9 to act as a kind of redundancy.

舉例來說，用這個影片要教大家的這種方法，你可以把資料儲存在 256 位元的區塊裡，每個區塊會用到 9 個位元，這 9 個位元用來做一種冗餘。

And the other 247 bits are free to carry whatever meaningful message or data that you want.

而另外的 247 個位元則可以自由地載入任何你想要的有意義訊息或資料。

And it will still be the case that if any bit gets flipped here, just by looking at this block and nothing more, a machine will be able to identify that there was an error and, and

而且即使這裡有任何一個位元被翻轉了，只要看這個區塊本身，機器就能辨識出有錯誤，而且

precisely where it was, so that it knows how to correct it.

精確知道錯誤在哪裡，這樣它就知道怎麼修正了。

說實話，這感覺就像魔法一樣。

And for this particular scheme, if two bits get flipped, the machine will at least be able to detect that there were two errors, though it won't know how to fix them.

對於這個特定的方法，如果兩個位元被翻轉了，機器至少能偵測到有兩個錯誤，雖然它不知道怎麼修正。

We'll talk a little bit later about how this scales for blocks with different sizes.

我們之後會再聊聊這種方法如何應用在不同大小的區塊上。

Methods that let you correct errors like this are known, reasonably enough, as error correction codes.

這種能讓你修正錯誤的方法，顧名思義，就叫做錯誤修正碼。

For the better part of the last century, this field has been a really rich source of surprisingly deep math that gets incorporated into devices we use every day.

在過去的將近一個世紀裡，這個領域一直是個非常豐富的數學寶庫，孕育出許多令人驚訝的深奧數學，並被應用在我們日常使用的各種裝置裡。

The goal here is to give you a very thorough understanding of one of the Earliest examples known as a hamming code.

這裡的目標是讓你透徹瞭解一個最早的範例，也就是漢明碼。

And by the way, the way I'm thinking about the structure of this video is less about explaining it as directly as possible, and

順帶一提，我規劃這個影片的方式，與其說是盡可能直接地解釋，

more a matter of prompting you to invent it for yourself with a little gentle guidance here and there.

不如說是引導你，在一些溫和的提示下，自己去發明它。

So when you feel like you see where it's going at some point, take that moment to pause.

所以，當你覺得似乎知道它要往哪個方向發展時，就停下來。

Actively predict what the scheme is going to be before I tell you.

在我告訴你之前，主動預測一下這個方法會是什麼。

Also, if you want your understanding to get down to the hardware level, Ben Eater has made a video in conjunction with this one showing you how to actually implement hamming codes on breadboards, which is extremely satisfying.

另外，如果你想把你的理解深入到硬體層面，Ben Eater 製作了一個與本影片搭配的影片，展示如何在麵包板上實際實現漢明碼，這真的非常令人滿足。

Now, you should know hamming codes are not as widely used as more modern codes like the Reed Solomon algorithm.

現在，你應該知道漢明碼不像 Reed Solomon 演算法等更現代的編碼那樣廣泛使用。

But there is a certain magic to the contrast between just how impossible this task feels at the start and how utterly reasonable it seems once you learn about Hamming.

但在任務一開始感覺多麼不可能，以及一旦你瞭解了漢明碼後，它又變得多麼合理之間，存在著一種奇妙的對比。

The basic principle of error correction is that in a vast space of all possible messages, only some subset are going to be considered valid messages.

錯誤修正的基本原則是，在所有可能訊息的廣闊空間中，只有一部分子集會被視為有效的訊息。

As an analogy, think about correctly spelled words versus incorrectly spelled words.

就像是正確拼寫的單字和拼錯的單字一樣。

Whenever a valid message gets altered, the receiver is responsible for correcting what they see back to the nearest valid neighbor, as you might do with a typo.

當一個有效的訊息被更改時，接收者會負責將看到的內容修正回最接近的有效鄰近訊息，就像你處理錯字一樣。

Coming up with a concrete algorithm to efficiently categorize messages like this, though, takes a certain cleverness.

不過，要設計出一個能有效分類這些訊息的具體演算法，需要一些巧思。

The story begins in the 1940s, when a young Richard Hamming was working for Bell Labs, and

故事始於 1940 年代，當時年輕的 Richard Hamming 在貝爾實驗室工作，

some of his work involved using a very big, expensive punch card computer that he had only limited access to.

他的部分工作是使用一臺非常大、非常昂貴的打孔卡電腦，而他能使用的時間非常有限。

And the programs he kept putting through it kept failing because every now and then, a bit would get misread.

他寫的程式不斷出錯，因為偶爾會有一個位元被誤讀。

Frustration being the crucible of invention, he got so fed up that he invented the world's first error correction code.

發明往往源於挫折，他實在受不了了，於是發明瞭世界上第一個錯誤修正碼。

There are many different ways to frame hamming codes, but

漢明碼有很多不同的闡述方式，但是

as a first pass, we're going to go through it the way that Hamming himself thought about them.

作為第一步，我們要用 Hamming 本人思考它們的方式來介紹。

Let's use an example that's simple, but not too simple.

我們來用一個簡單但又不至於太簡單的例子。

We'll number the positions of these bits from 0 up to 15.

我們會將這些位元的位置從 0 編號到 15。

The actual data that we want to store is only going to make up 12 of these bits, while four of the positions are going to be reserved as a kind of redundancy.

我們實際想儲存的資料只會佔其中 12 個位元，而有四個位置將被保留作為一種冗餘。

The word redundant here doesn't simply mean copyright.

這裡的「冗餘」這個詞，可不是單純指複製。

After all, those four bits don't give us enough room to blindly copy the data.

畢竟，這四個位元並沒有足夠的空間讓我們直接複製資料。

Instead, they'll need to be a much more nuanced and clever kind of redundancy, not adding any new information, but

相反地，它們需要一種更細緻、更聰明的冗餘方式，不是增加新資訊，而是

You might expect these four special bits to come nicely packaged together, maybe at the end or something like that.

你可能會預期這四個特殊位元會被整齊地打包在一起，也許放在最後面之類的。

But as you'll see, having them sit in positions which are powers of two allows for something that's really elegant by the end.

但你會發現，讓它們位在是 2 的次方的位置，最終能實現非常優雅的效果。

It also might give you a little hint about how this scales for larger blocks.

這也可能給你一點關於它如何擴展到更大區塊的提示。

Also, technically, it ends up being only 11 bits of data.

另外，嚴格來說，它最終只會有 11 個位元資料。

You'll find there's a mild nuance for what goes on at position zero.

你會發現，位置零的部分會有一點點細微的差別。

Like any error correction algorithm, this will involve two.

就像任何錯誤修正演算法一樣，這會牽涉到兩個部分。

A sender who's responsible for setting these four special bits, and

一個是負責設定這四個特殊位元的傳送者，另一個

then a receiver who's responsible for performing some kind of check and then correcting the errors.

則是負責執行某種檢查然後修正錯誤的接收者。

Of course, the words sender and receiver really refer to machines or software that's doing all the checks.

當然，「傳送者」和「接收者」這兩個詞，其實是指執行所有檢查的機器或軟體。

And the idea of a message is meant really broadly to include things like storage.

而「訊息」這個概念，其實是廣泛地包含儲存等事物。

After all, storing data is the same thing as sending a message just from the past to the future, instead of from one place to another.

畢竟，儲存資料跟傳送訊息是一樣的，只是從過去傳到未來，而不是從一個地方傳到另一個地方。

But before we can dive in, we need to talk about a related idea which was fresh on Hamming's mind in the time of his discovery.

不過，在我們深入探討之前，有個相關的概念，是漢明在發現當時腦中一直想著的，我們需要先聊聊。

A method which lets you detect any single bit errors, but

一種可以偵測出任何單一位元錯誤的方法，但

not to correct them, known in the business as a parity check.

卻無法修正它們，在業界裡稱為同位檢查。

For a parity check, we separate out only one single bit that the sender is responsible for tuning, and

對於同位檢查，我們會另外分出一個位元，由傳送者負責調整，

而其他位元則可以自由地傳送訊息。

The only job of this special bit is to make sure that the total number of ones in the message is an even number.

這個特殊位元唯一的任務，就是確保訊息中「一」的總數是偶數。

So, for example, right now, that total number of ones is seven.

所以，舉例來說，現在「一」的總數是七。

So the sender needs to flip that special bit to be a one, making the count even.

所以傳送者需要將這個特殊位元翻成「一」，讓總數變成偶數。

But if the block had already started off with an even number of ones, and

但如果這個區塊一開始就已經有偶數個「一」了，

then this special bit would have been kept at a zero.

那麼這個特殊位元就會維持在「零」。

This is pretty simple, deceptively simple.

這其實很簡單，簡單到有點出乎意料。

But it's an incredibly elegant way to distill the idea of change anywhere in a message to be reflected in a single bit of information.

但這是一種非常巧妙的方式，能將訊息中任何地方的變動，都濃縮成一個位元來反映。

Notice if any bit of this message gets flipped either from 0 to 1 or 1 to 0, it changes the total count of ones from being even to being odd.

你會發現，如果訊息中的任何一個位元被翻轉，從「零」變「一」或從「一」變「零」，都會讓「一」的總數從偶數變成奇數。

So if you're the receiver, you look at this message and you see an odd number of ones, you can know for sure that some error has occurred, even though you might have no idea where it was.

所以，如果你是接收者，看到這個訊息，發現「一」的總數是奇數，你就能確定一定發生了錯誤，即使你不知道是哪個部分出了問題。

In the jargon, whether a group of bits has an even or an odd number of ones is known as its parity.

在專業術語裡，一組位元擁有偶數個或奇數個「一」，就稱為它的「同位元」。

You could also Use numbers and say the parity is 0 or 1, which is typically more helpful once you start doing math with the idea.

你也可以用數字來表示，同位元是「零」或「一」，這在你開始進行相關數學運算時會更有幫助。

And this special bit that the sender uses to control the parity is called the parity.

而傳送者用來控制同位元的這個特殊位元，就叫做「同位元」。

And actually we should be if the receiver sees an odd parity, it doesn't necessarily mean there was just one error.

實際上，如果接收者看到同位元是奇數，並不一定代表只有一個錯誤。

There might have been three errors or five or any other odd number, but

可能發生了三個錯誤，或是五個，或是任何其他奇數個錯誤，但是

they can know for sure that it wasn't zero.

On the other hand, if there had been two errors or any even number of errors, that final count of ones would still be even.

另一方面，如果發生了兩個錯誤，或是任何偶數個錯誤，最後的「一」的總數還是會是偶數。

So the receiver can't have full confidence that an even count necessarily means the message is error free.

所以接收者無法完全確定偶數總數就一定代表訊息沒有錯誤。

You might complain that a message which gets messed up by only two bit flips is pretty weak, and

你可能會抱怨，一個訊息只因為兩個位元翻轉就出錯，這太弱了，

Keep in mind though, there is no method for error detection or correction that could give you 100% confidence that the message you receive is the one that the sender intended.

不過要記得，沒有任何一種錯誤偵測或修正方法能讓你百分之百確定收到的訊息就是傳送者想要的。

After all, enough random noise could always change one valid message into another valid message just by pure chance.

畢竟，足夠的隨機雜訊總有可能純粹偶然地將一個有效的訊息變成另一個有效的訊息。

Instead, the goal is to come up with a scheme that's robust up to a certain maximum number of errors, or maybe to reduce the probability of a false positive like this.

相反地，目標是設計一個能應對特定最大錯誤數的方案，或者也許是降低這種誤判的機率。

Parity checks on their own are pretty weak.

But by distilling the idea of change across a full message down to a single bit, what they give us is a powerful building block for more sophisticated schemes.

但是透過將整個訊息的改變概念濃縮成一個位元，它們就成了更複雜方案的強大基礎。

For example, as Hamming was searching for a way to identify where an error happened, not just that it happened, his key insight was that if you apply some parity checks not to the full message and but to certain carefully selected subsets, you can ask a more refined series of questions that pin down the location of any single bit error.

舉例來說，當漢明在尋找一種方法來辨識錯誤發生的位置，而不僅僅是錯誤發生了，他的關鍵洞見是，如果你對部分訊息而非整個訊息進行一些精心挑選的子集同位元檢查，你就可以提出一連串更精確的問題，來鎖定任何單一位元錯誤的位置。

The overall feeling is a bit like playing a game of 20 questions, asking yes or no queries that chop the space of possibilities in half.

整體感覺有點像在玩「二十個問題」的遊戲，提出「是」或「否」的問題，每次都能將可能性空間縮減一半。

For example, let's say we do a parity check just on these eight bits, all of the odd numbered positions.

舉個例子，假設我們只對這八個位元進行同位元檢查，也就是所有奇數位置的位元。

Then if an error is detected, it gives the perceiver a little more information about where specifically the error is, namely that it's in an odd position.

那麼，如果偵測到錯誤，接收者就能獲得更多關於錯誤具體位置的資訊，也就是它在一個奇數位置。

If no error is detected among those eight bits, it either means there's no error at all, or it sits somewhere in the even positions.

如果這八個位元中沒有偵測到錯誤，那就表示根本沒有錯誤，或者錯誤就出現在偶數位置。

You might think that limiting a parity check to half the bits makes it less effective, but

你可能會覺得，將同位元檢查限制在一半的位元上會降低它的有效性，但是

when it's done in conjunction with other well chosen checks, it counterintuitively gives us something a lot more powerful to actually set up that parity Check.

當它與其他精心挑選的檢查結合時，它反直覺地給了我們更有力的工具來實際設定那個同位元檢查。

Remember, it requires earmarking some special bit that has control for the parity of that full group.

請記住，這需要指定一個具有該完整群組同位元控制權的特殊位元。

Here, let's just choose position number one.

在這裡，我們就選擇第一號位置。

So, for the example shown, the parity of these eight bits is currently odd.

所以，以上面這個例子來說，這八個位元的同位元目前是奇數。

字幕列表影片播放

漢明碼是什麼？差錯修正的起源！ (But what are Hamming codes? The origin of error correction)

specific

assume

matter

flip