---
title:
image:
description:
tags: NCKU Class
---
# # [Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA&t=135)
Have you ever wondered how it’s possible
to scratch a CD or DVD and still have it play

back whatever it’s storing?

The scratch really does affect the 1’s and
0’s on the disc, so it reads off different

data from what was stored, but unless it’s
really scratched up, the bits it reads are

decoded into precisely the same file that
was encoded on to it, a bit-for-bit copy,

despite all those errors.

There’s a whole pile of mathematical cleverness
that allows us to store data, and just as

importantly to transmit it, in a way that’s
resilient to errors.

Well, actually, it doesn’t take too much
cleverness to come up with a way to do this.

Any file, whether it’s a video, or sound,
or text, code, an image, whatever, is ultimately

stored as a sequence of 1’s and 0’s, and
a simple strategy to correct any bit that

gets flipped would be to store three copies
of each bit.

Then the machine reading the 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 that space given up,
there’s no strong guarantee about what happens

if more than 1 bit gets flipped.

The much more interesting question is how
to make it so that errors can be corrected

while giving up as little space as possible.

For example, using the method you’ll learn
about in this video, you could store your

data in 256-bit blocks, where each block uses
nine bits –Nine!– to act as a kind of

redundancy, the other 247 bits are free to
carry whatever meaningful message or data

you want.

And it will still be the case that if a bit
gets flipped, just by looking at this block

and nothing more, a machine will be able to
identify that there was an error and precisely

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

And honestly, that feels like magic.

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 later about how this scales for
blocks of a different size.

Methods that let you correct errors like this
are known, reasonably enough, as “Error

correction code.”

For the better part of the last century, this
field has been a really rich source of surprisingly

deep math being incorporated into devices
we all 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

yourself, with some a little gentle guidance
here and there.

02;41
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 that 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.
Hamming codes 其實在現代並不用的那麼廣泛，例如 Reed Solomon algorithm
就比他用得更廣(CD/DVD)。

But there is a certain magic to the contrast
between just how impossible the task feels

at the start, and how utterly reasonable it
is once you learn about Hamming.
但是要了解那更高階的演算法，你需要先了解 Hamming

The basic principle of error correction is
that in a vast space of all possible messages,

03:22
only some subset are going to be considered
valid messages.
偵錯的基本原理是，有用的資訊是所以資訊組合的子集合。

As an analogy, think of correctly spelled
words vs 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, take
a certain cleverness.
但是，提出一種具體的算法來對此類消息進行有效的分類需要一定的技巧。

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

and some of his work involved using a very
big very expensive punchcard computer that

he had only limited access to.
故事始於1940年代，當時年輕的理查德·漢明（Richard Hamming）
為貝爾實驗室（Bell Labs）工作，
他的一些工作涉及使用一台非常昂貴的大型打孔卡計算機，
而他只能使用這種計算機。

And the programs he kept putting through it
kept failing because every now and then a
bit would get misread.
他不斷嘗試的程序一直失敗，因為有時會被誤讀。

Frustration being the crucible for invention,
he got so fed up that he invented error correction
codes.
挫敗感是發明的關鍵，他受夠了以至於發明了糾錯碼。

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代碼的方式有很多，但是作為第一步，
我們將以Hamming自己對它們的思考方式進行研究。

Let’s use an example that’s simple, but
not too simple: A block of 16 bits.
讓我們用一個簡單但不太簡單的示例：一個16位的塊。

04:22
We’ll number the positions of these bits
from 0 up to 15.
我們將這些位的位置編號從0到15。

The actual data we want to store is only going
to make up 12 of these bits, while 4 of the
positions will be reserved as a kind of redundancy.
我們要存儲的實際數據僅由這些位中的12位組成，
而其中的4個位置將被保留作為一種驗證(冗餘)。

The word “redundant” here doesn’t simply
mean copy, 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 adding resilience.
相反，它們將需要是一種更加細微和巧妙的冗餘，
而不是添加任何新信息，而是增加彈性。

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 2 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; you’ll find there’s a mild

nuance for what goes on with position 0, but
don’t worry about that for now.
同樣，從技術上講，它最終僅是11位數據。
您會發現位置0的情況有些細微差別，但現在不必擔心。

Like any error correction algorithm, this
will involve two players: A sender who is

responsible for setting these four special
bits, and then a receiver who is responsible

for performing some checks and correcting
any errors.
像任何糾錯算法一樣，這將涉及兩個參與者：
負責設置這四個特殊位的發送者，
以及負責執行某些檢查並糾正任何錯誤的接收者。

Of course, the words “sender” and “receiver”
really refer to machines or software that's

doing all these checks, and the idea of a
message is meant really broadly, to include

things like storage.
當然，“發送者”和“接收者”這兩個詞
真正指的是進行所有這些檢查的機器或軟件，
消息的含義實際上是廣義的，包括存儲之類的內容。

After all, storing data is the thing as sending
a message, just from the past to the future

instead of from one place to another.
畢竟，存儲數據就像發送一條消息一樣，
只是從過去到未來，而不是從一個地方到另一個地方。

05:44
So that’s the setup, 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 error, but not to correct
them, known in the business as a “parity

check”.
這就是設置，但是在深入研究之前，我們需要談談一個相關的想法，
該想法在漢明被發現時就在他腦海中浮現出來，
這種方法可以讓您檢測任何一位錯誤，但不能糾正它們 ，
在業務中稱為“奇偶校驗”。

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

for tuning, and the rest are free to carry
a message.
對於奇偶校驗，
只需利用到其中一個 bit 即可
其餘部分可自由攜帶消息。

The only job of this special bit is to make
sure the total number of 1’s in the message

is an even number.
此特殊位的唯一工作是確保消息中的1的總數為偶數。

For example, right now that total number of
1’s is 7, that's odd, so the sender needs

to flip that special bit to be a 1, making
the count even.
例如，現在1的總數為7，這很奇怪，
因此發送者需要將該特殊位翻轉為1，使計數相等。

But if the block had already started off with
an even number of 1’s, then this special

bit would have been kept at a 0.
但是，如果該塊已經以偶數1開始，則該特殊位應保持為0。

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 1’s from being even to being
odd.
請注意，如果此消息的任何內容被翻轉，
從0到1或從1到0，它將1的總數從偶數更改為奇數。

So if you're the receiver, you look at this
message, and you see an odd number of 1’s,

you can know, for sure, that some error occurred,
even though you might have no idea where it

was.
因此，如果您是接收者，請查看此消息，
然後看到奇數1，即使您可能不知道它在哪裡，
也可以肯定地知道發生了一些錯誤。

In the jargon, whether a group of bits has
an even or odd number of 1’s is known as

its “parity”.
用行話來說，一組位是偶數還是奇數均為1，就稱為“奇偶校驗”。

You could also use numbers and say that the
parity is 0 or 1, which is typically more

helpful once you start doing math with the
idea.
初學者可以用 0 or 1 來認知 parity

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

bit”.
發送方用來控制奇偶校驗的特殊位稱為“奇偶校驗位”。

And actually, we should be clear, if the receiver
sees an odd parity, it doesn't necessarily

mean there was just 1 error.
實際上，我們應該清楚，如果接收方看到奇數奇偶校驗，則不一定意味著只有1個錯誤。

There might have been 3 errors, or 5, or any
other odd number, but they can know for sure

that it wasn’t 0.
可能有3個錯誤，5個或其他奇數，但他們可以肯定地知道它不是0(因為它是錯的)。

On the other hand, if there had been 2 errors,
or any even number of errors, that final count

of 1’s would still be even, so the receiver
can’t have full confidence that an even

count necessarily means the message is error-free.
另一方面，如果存在2個錯誤或任何偶數個錯誤，則最終的1計數仍將是偶數，因此接收者無法完全確定偶數必然意味著該消息沒有錯誤。

You might complain that a method which gets
messed up by only two bit flips is pretty

weak, and you would be absolutely right!
您可能會抱怨僅兩次翻轉就搞砸了的方法非常弱，您絕對正確！

07:52
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 the sender intended.
但是請記住，沒有錯誤檢測或糾正方法可以使您100％確信收到的消息是發件人想要的。

After all, enough random noise can 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 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.
奇偶校驗本身是很弱的，但是通過將整個消息中的變更思想精簡到單個位，它們為我們提供了強大的構建更複雜方案的基礎。

08:40
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, 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.
例如，當漢明（Hamming）正在尋找一種方法來識別錯誤發生的地方，而不僅僅是錯誤發生的時候，他的主要見解是，如果您對某些消息（而不是整個消息）進行某些奇偶校驗，而不是對某些消息進行仔細地選擇，則可以 提出一系列更精確的問題，以查明任何單位錯誤的位置。

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
on just these 8 bits, all the odd-numbered

positions.
總體感覺有點像玩20個問題的遊戲，問是或否的查詢將可能性空間減半。 例如，假設我們僅對這8位（所有奇數位置）進行奇偶校驗。

Then if an error is detected, it gives the
receiver 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 8 bits,
it either means there's no error at all, or

it sits somewhere in the even position.
如果在這8位中沒有檢測到錯誤，則意味著根本沒有錯誤，或者它位於偶數位置。

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 parity checks, it counterintuitively

gives us something 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 1.
請記住，要實際設置該奇偶校驗，需要指定一些特殊的位來控制整個組的奇偶校驗。 在這裡，我們只選擇位置編號1。

So for the example shown, the parity of these
8 bits is currently odd, so the sender is

responsible for toggling that parity bit,
and now it's even.
因此，對於所示示例，這8位的奇偶校驗當前是奇數，因此發送方負責切換該奇偶校驗位，而現在是偶數。

This is only one out of four parity checks
we’ll do.

The second check is going to be among the
8 bits on the right half of the grid, at least

as we've drawn it here.
這只是我們要進行的四項奇偶校驗中的一項。 第二個檢查將位於網格右半部分的8位中，至少正如我們在此處繪製的那樣。

This time, we might use position number 2
as a parity bit.
這次，我們可以將位置編號2用作奇偶校驗位。

So these 8 bits already have an even parity,
and the sender can feel good leaving that

bit number 2 unchanged.
因此，這8位已經具有偶數奇偶校驗，並且發送方可以感覺很好，而保持第2位不變。

Then, on the other end, if the receiver checks
the parity of this group and they find that

it’s odd, they’ll know that the error
is somewhere among these 8 bits on the right.
然後，在另一端，如果接收方檢查了該組的奇偶校驗並且發現奇偶校驗，則他們將知道該錯誤位於右側的這8位中。

Otherwise, it means either there's no error,
or the error is somewhere on the left half.
否則，這意味著沒有錯誤，或者錯誤在左半部分。

Or I guess there could have been two errors,
but for right now we’re going to assume
或者我猜可能有兩個錯誤，但是現在我們要假設

that there’s at most one error in the entire
block; things break down completely for more

than that.
整個區塊中最多只有一個錯誤； 事情完全不止於此。

Here, before looking at the next two checks,
take a moment to think about what these first

==two allow us to do when you consider them
together.
在這裡，在查看接下來的兩個檢查之前，花點時間考慮一下當您將它們一起考慮時，前兩個允許我們做什麼。

Let's say you detect an error among the odd
columns, and among the right half.
假設您在奇數列和右半數之間檢測到錯誤。

It necessarily means the error is somewhere
in the last column.
這必然意味著錯誤在最後一列中。

If there was no error in the odd column, but
there was one in the right half, well that

tells you it's in the second to last column.
如果在奇數列中沒有錯誤，但是在右半部分中有一個，那麼這告訴您它在倒數第二列中。

Likewise, if there is an error in the odd
columns but not the right half, you know that

it's somewhere in the second column.
同樣，如果奇數列中有錯誤，但右半部分中沒有，則您知道它在第二列中。

==And then, if neither of those two parity checks detects anything, it means the only place an error could be is in that leftmost column, but it also might simply mean there’s no error at all.
然後，如果這兩個奇偶校驗檢查均未檢測到任何東西，則意味著唯一的錯誤可能在該最左側的列中，但這也可能僅意味著完全沒有錯誤。==

Which is all a rather belabored way to say
that two parity checks let us pin down the

column.
說兩個奇偶校驗讓我們固定列是一種相當荒謬的方式。

From here, you can probably guess what follows.

We do basically the same thing, but for the
rows.
從這裡，您可能會猜到接下來的事情。 我們基本上做相同的事情，只是對於行。

There’s going to be a parity check on the
odd rows, using position 4 as a parity bit.
將使用位置4作為奇偶校驗位，對奇數行進行奇偶校驗。

So in this example, that group already has
even parity, so bit 4 would be set to a 0.

And finally there's a parity check on the
bottom two rows, using position 8 as a parity

bit.
因此，在此示例中，該組已經具有奇偶校驗，因此將第4位設置為0。最後，使用位置8作為奇偶校驗位，對最後兩行進行了奇偶校驗。

In this case, it looks like the sender needs
to turn on bit 8 on in order to give that

group an even parity.
在這種情況下，發送方似乎需要打開第8位，以使該組具有均勻的奇偶校驗。

Just as the first two checks let us pin down
the column, these next two let you pin down

the row.
就像前兩個檢查使我們固定該列一樣，後兩個檢查使您固定該行。

As an example, imagine that during transmission
there’s an error at, say position 3.
舉例來說，假設在傳輸過程中，位置3出現錯誤。

Well, this affects the first parity group,
and it also affects the second parity group,

so the receiver knows that there's an error
somewhere in that right column.
好吧，這會影響第一個奇偶校驗組，並且也會影響第二個奇偶校驗組，因此接收方知道在該右列中某處存在錯誤。

But it doesn’t affect the third group, and
it doesn't affect the fourth group.
但這不會影響第三組，也不會影響第四組。

And that lets the receiver pinpoint the error
up to the first row, which necessarily means

position 3, so they can fix the error.
這樣，接收器就可以將錯誤精確定位到第一行，這必然意味著位置3，因此他們可以糾正錯誤。

You might enjoy taking a moment to convince
yourself that the answers to these four questions

really will always let you pin down a specific
location, no matter where they turn out to

be.
您可能會花一點時間說服自己，這四個問題的答案實際上總是會讓您確定特定的位置，無論它們位於何處。

In fact, the astute among you might even notice
a connection between these questions and binary

counting.
實際上，你們之間的精明甚至可能會注意到這些問題和二進制計數之間的聯繫。

And if you do, again let me emphasize, pause,
try for yourself to draw the connection before

I spoil it.
如果您願意，請再次強調一下，暫停一下，嘗試在我破壞連接之前自己畫一下連接。

If you’re wondering what happens if a parity
bit itself gets affected…well you can just

try it.
如果您想知道如果校驗位本身受到影響會發生什麼……那麼您可以嘗試一下。

Take a moment to think about how any error
among these four special bits is going to

be tracked down just like any other, with
the same game of 4 questions.
花點時間考慮一下，如何使用四個問題進行相同的博弈，如何像追尋其他四個特殊位一樣追查任何錯誤。

You might also enjoy anticipating how this
scales.

If we used a block of size 256 bits, for example,
in order to pin down a location, you need

only 8 yes or no questions to binary search
your way down to some specific spot.
您可能還會喜歡預期如何擴展。

例如，如果我們使用大小為256位的塊，
為了確定位置，您只需要8個是或否問題就可以對特定位置進行二進制搜索。

And remember, each question requires giving
up only a single bit to set the appropriate

parity check.
記住，每個問題只需要放棄一點就可以設置適當的奇偶校驗。

Some of you may already see it, but we’ll
talk later about the systematic way to find

what these questions are in just a minute
or two.
你們中的有些人可能已經看到了，但是稍後我們將討論一種系統的方法，可以在一兩分鐘內找到這些問題。

Hopefully, this sketch is enough to appreciate
the efficiency of what we’re developing

here.
希望此草圖足以了解我們在此開發的效率。

Everything except for those 8 highlighted
parity bits, can be whatever you want it to

be, carrying whatever message or data you
want.
除了那8個突出顯示的奇偶校驗位以外的所有內容，都可以是您想要的任何形式，可以攜帶所需的任何消息或數據。

The 8 bits are “redundant” in the sense
that they’re completely determined by the

rest of the message, but it’s in a much
smarter way than simply copying the message

as a whole.
這8位是“冗餘”，從某種意義上說，這8位完全由消息的其餘部分確定，但這比簡單地複制整個消息要聰明得多。

And still, for so little given up, you would
be able to identify and fix any single bit

error.
而且，只需付出很少的代價，您就可以識別並修復任何單個錯誤。

Well...almost.

Okay, so, the one problem here is that if none of the four parity checks detect an error, meaning that the specially selected subsets of eights bits all have even parities just like the sender intended, then it either means there was no error at all, or it narrows us down into position 0.
好的，所以這裡的一個問題是，如果四個奇偶校驗中沒有一個檢測到錯誤，這意味著像發送方所預期的那樣，經過特殊選擇的八位比特的子集都具有偶校驗，那麼這要么意味著就沒有錯誤。 ，或者將我們縮小到位置0。

You see, with four yes or no questions, we
have 16 possible outcomes for our parity checks.

And at first, that feels perfect for pinpointing
1 of the 16 positions in the block.

But you also need to communicate a 17th outcome,
the “no error” condition.
您會看到，有四個是或否的問題，我們的奇偶校驗檢查有16種可能的結果。

首先，這對於在塊中精確定位16個位置中的1個感覺非常理想。

但是，您還需要傳達第17個結果，即“沒有錯誤”的情況。

The solution here is actually pretty simple:
Just forget about 0th bit entirely.

So when we do our four parity checks, and
we see that they're all even, it unambiguously

means that there is no error.
實際上，這裡的解決方案非常簡單：完全忘記第0位。

因此，當我們進行四個奇偶校驗檢查時，我們看到它們都是偶數，這無疑意味著沒有錯誤。

What that means, is that rather than working
with a 16-bit block, work with a 15-bit block,

where 11 of the bits are free to carry a message,
and 4 of them are there for redundancy.

And with that, we now have what people in
the business would refer to as a “(15, 11)

Hamming code”.
這意味著，不是使用16位塊，而是使用15位塊，其中11位可以自由攜帶消息，其中4位用於冗餘。

這樣，我們現在有了業務中的人們將其稱為“（15，11）Hamming代碼”。

That said, it is nice to have block size that's
a clean power of 2, and there’s a clever

way that we can keep that 0th bit around and
get it to do a little extra work for us.
就是說，最好將塊大小保留為2的整數次冪，並且有一種聰明的方法可以使第0位保持不變，並使它為我們做一些額外的工作。

If we use it as a parity bit across the whole
block, it lets us actually detect, even though

we can't correct, 2-bit errors.

Here’s how it works.
如果我們將其用作整個塊的奇偶校驗位，則即使我們無法糾正2位錯誤，它也可以使我們實際檢測到。

運作方式如下。

After setting those four special error-correcting
bits, we set that 0th bit so that the parity

of the full block is even, just like a normal
parity check.
設置完這四個特殊的糾錯位後，我們將第0位設置為全塊的奇偶校驗是偶數，就像普通的奇偶校驗一樣。

Now if there’s a single-bit error, then
the parity of the full block toggles to be

odd, but we would catch that anyway thanks
to our four error-correcting checks.
現在，如果存在一個單位錯誤，則整個塊的奇偶校驗會切換為奇數，但是由於我們進行了四次糾錯檢查，因此無論如何我們都會抓住這一點。

However, if there are two errors, then the
overall parity is going to toggle back to

being even, but the receiver will still see
that there’s been at least some error because

of what's going on with the four usual parity
checks.
但是，如果有兩個錯誤，則總體奇偶校驗將切換回偶數，但是由於四種常見的奇偶校驗檢查的結果，接收者仍然會看到至少存在一些錯誤。

So if they notice an even parity overall, but something nonzero happening with the other checks, it tells them there were at least two errors.
因此，如果他們發現總體上是均勻的奇偶校驗，但其他檢查發生了非零的變化，則表明它們至少存在兩個錯誤。

Isn’t that clever?
那不是很聰明嗎？

Even though we can’t correct those two-bit errors, just by putting that one little bothersome 0th bit to work, it lets us detect them.
即使我們無法糾正這兩位錯誤，也只需將那一個令人煩惱的第0位放上去，它就能讓我們檢測到它們。

This is pretty standard, it's known as an
“extended” hamming code.

Technically speaking, you now have a full
description of what a Hamming code does, at

least for the example of a 16-bit block.
這是相當標準的，被稱為“擴展”漢明碼。

從技術上講，至少對於16位塊的示例，現在您已經獲得了漢明碼的功能的完整說明。

But I think you'll find it more satisfying to check your understanding and solidify everything up to this point by doing one full example from start to finish yourself.
但是，我認為通過從頭到尾做一個完整的例子，檢查自己的理解並鞏固到目前為止的一切，會使您感到更加滿意。

I’ll step through it with you, though, so you can check yourself.
不過，我會與您一起逐步解決，以便您檢查一下自己。

To set up a message, whether that’s a literal message that you’re transmitting over space, or some data that you want to store over time, the first step is to divide it up into 11-bit chunks.
要設置一條消息，無論是通過空間傳輸的文字消息，還是要隨時間存儲的某些數據，第一步就是將其劃分為11位塊。

Each chunk is going to get packaged into an error-resistant 16-bit block, so let’s take this one as an example and actually work it out.
每個塊都將打包到一個抗錯誤的16位塊中，因此讓我們以它為例進行實際計算。

Go ahead, actually do it, pause and try putting together this block ....okay, you ready?

繼續，實際上是這樣做，暫停並嘗試將這個塊放在一起....好吧，您準備好了嗎？

Remember, position 0 along with all the powers of 2 are reserved for error-correction duty, so you start by placing the message bits in all of the remaining spots, in order
請記住，位置0和2的所有冪均保留用於糾錯，因此您首先應按順序將消息位放在所有其餘位置。

You need this group to have even parity, which it already does, so you should have set the parity bit in position 1 to be a 0.
您需要使該組具有偶校驗，而這已經做到了，因此您應該將位置1的校驗位設置為0。

The next group starts off with odd parity,
so you should have set its parity bit to 1.

The group after that starts with odd parity,
so again you should have set it’s parity

bit to 1.
下一組以奇校驗開始，因此您應該將其校驗位設置為1。

之後的組以奇偶校驗開始，因此您應該再次將其校驗位設置為1。

And the final group also has odd parity, meaning
we set that bit in position 8 to be a 1.
最後一組也具有奇偶校驗，這意味著我們將位置8的位設置為1。

And then, as the final step, the full block
now has even parity, meaning that you can

set that bit number 0, the overarching parity
bit, to be 0.
然後，作為最後一步，完整塊現在具有奇偶校驗，這意味著您可以將第0位（總體奇偶校驗位）設置為0。

So as this block is sent off, the parity of
the four special subsets, and the block as

a whole, will all be even, or zero.
因此，在發送該塊時，四個特殊子集的奇偶校驗以及整個塊的奇偶性將全部為偶數或零。

As the second part of the exercise, let’s have you play the role of the receiver.

Of course, that would mean you don’t already know what this message is; maybe some of you memorized it but, let’s assume that you haven’t.
作為練習的第二部分，讓我們扮演接收者的角色。

當然，這意味著您還不知道該消息是什麼； 也許有些人記住了，但是，假設您沒有記住。

What I’m going to do is change either zero, one or two of the bits in that block, and then ask you to figure out what it is that I did.
我要做的是更改該塊中的零，一位或兩位，然後請您弄清楚我做了什麼。

So, again, pause and try working it out.
因此，再次暫停並嘗試解決。

...okay, so you as the receiver now check the first parity group and you can see that it’s even, so any error that exists would have to be in an even column.
...好吧，作為接收者，您現在檢查第一個奇偶校驗組，您可以看到它是偶數，因此存在的任何錯誤都必須在偶數列中。

The next check gives us an odd number, telling us both that there’s at least one error, and narrowing us down into this specific column.

The third check is even, chopping down the possibilities even further.
接下來的檢查為我們提供了一個奇數，告訴我們至少存在一個錯誤，然後將我們縮小到此特定列。

第三次檢查是偶數，進一步削減了可能性。

And the last parity check is odd, telling us there’s an error somewhere in the bottom, which by now we can see must be in position number 10.
最後一次奇偶校驗很奇怪，告訴我們底部存在某個錯誤，現在我們可以看到它必須在位置10處。

What’s more, the parity of the whole block is odd, giving us confidence that there was one flip and not two (if it’s three or more, all bets are off).
更重要的是，整個區塊的奇偶性很奇怪，這使我們確信只有一次擲骰而不是兩次擲骰（如果大於或等於3，則所有投注均無效）。

After correcting that bit number 10, pulling out the 11 bits that were not used for correction gives us the relevant segment of the original message, which if you rewind and compare, is indeed exactly what we started the example with.
在糾正了第10位之後，取出11個未用於糾正的位將為我們提供原始消息的相關部分，如果您倒帶並進行比較，實際上正是我們從示例開始的。

And now that you know how to do all this by hand, I’d like to show you how you can carry out the core part of all of this logic with a single line of python code.
現在，您知道如何手動完成所有這些操作，我想向您展示如何用一行Python代碼執行所有這些邏輯的核心部分。

You see, what I haven’t told you yet is just how elegant this algorithm really is, how simple it is to get a machine to point to the position of an error, how to systematically scale it, and how we can frame all of this as one single operation rather than multiple separate checks.
您看，我尚未告訴您的是該算法的真正優雅之處，使機器指向錯誤位置的簡單程度，如何系統地縮放錯誤以及如何構建所有 這是一個單一的操作，而不是多個單獨的檢查。

To see what I mean, come join me in part 2.
要了解我的意思，請加入我的第二部分。