Name: ハム符号とは？誤り訂正の起源 (But what are Hamming codes? The origin of error correction)
Uploaded: 2026-01-07T04:47:41.000Z
Duration: 20 min 5 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

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.

傷はディスク上のones and zerosに実際に影響を与えるため、保存されていたものとは異なるデータを読み取ってしまいます。

様態の副詞

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.

しかし、ひどく傷ついていない限り、読み取られたbitsは、エンコードされたものと全く同じファイルにdecodedされ、bit単位のコピーとなります。

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.

ビデオ、サウンド、テキスト、コード、画像など、どんなファイルも、最終的にはones and zerosのシーケンスです。

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

そして、ビットが反転した場合にそれを訂正する簡単な戦略は、各ビットのコピーを3つ保存することです。

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.

そうすれば、このファイルを読み取る機械は、これらの3つのコピーを比較し、不一致がある場合は常に3つの中から最良の2つを選択できます。

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

しかし、それはスペースの3分の2をリダンダンシーに使うことを意味します。

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.

そして、この特定の方式では、2つのビットが反転した場合、機械は少なくとも2つのエラーがあったことを検出できますが、それを修正する方法はわかりません。

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.

この分野は、過去1世紀のほとんどの間、私たちが毎日使うデバイスに組み込まれる、驚くほど深い数学の豊かな源泉となってきました。

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

ここでは、ハミング符号として知られる最も初期の例の1つを、非常に深く理解していただくことを目指します。

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.

さて、ハミング符号は、リード・ソロモン・アルゴリズムのようなより現代的な符号ほど広くは使われていないことを知っておくべきです。

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年代に始まり、若いリチャード・ハミングがベル研究所で働いていた頃、

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.

最初のアプローチとして、ハミング自身がそれらをどのように考えたかという方法で進めていきましょう。

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ビットだけを占め、4つの位置は一種のリダンダンシーとして予約されます。

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.

結局のところ、その4ビットだけでは、データを盲目的にコピーするのに十分なスペースはありません。

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.

これらの4つの特別なビットは、きれいにパッケージ化されて、おそらく最後の方に来るだろうと期待するかもしれません。

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.

どんなエラー訂正アルゴリズムでもそうですが、これには2つが関わってきます。

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

これらの4つの特別なビットを設定する責任を持つ送信者と、

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.

この特別なビットの唯一の仕事は、メッセージ中の1の合計数が偶数であることを確認することです。

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

ですから、例えば、今現在、1の合計数は7です。

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

したがって、送信者はこの特別なビットを1に反転させて、カウントを偶数にする必要があります。

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

しかし、もしブロックがすでに奇数の1で始まっていた場合、

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

その特別なビットはゼロのままでした。

This is pretty simple, deceptively 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.

しかし、メッセージのどこかの変化を、たった1つの情報ビットに反映させるという、信じられないほどエレガントな方法です。

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.

このメッセージのどのビットが0から1、または1から0に反転しても、1の合計数が偶数から奇数に変わることに注意してください。

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.

ですから、受信者はこのメッセージを見て、1の数が奇数であれば、どこにあるかは分からなくても、何らかのエラーが発生したことを確実に知ることができます。

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

専門用語では、ビットのグループが1の数が偶数か奇数かは、そのパリティとして知られています。

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.

数値を使って、パリティが0または1であると言うこともできます。これは、この考え方で数学を始めると、通常はより役立ちます。

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.

そして実際、受信者が奇数のパリティを見た場合、それは必ずしも1つのエラーがあったことを意味するわけではありません。

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

3つ、5つ、あるいは他の奇数のエラーがあったかもしれませんが、

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.

一方、2つのエラー、または任意の偶数個のエラーがあった場合、1の最終的なカウントは偶数のままになります。

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

たった2ビットの反転でメッセージが台無しになるのはかなり弱いと不満を言うかもしれませんが、

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.

ただし、受信したメッセージが送信者が意図したものであると100%確信できるエラー検出または訂正方法はないことを覚えておいてください。

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.

しかし、メッセージ全体にわたる変化という考え方を1ビットに凝縮することで、より洗練されたスキームのための強力なビルディングブロックを提供してくれます。

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.

全体的な感覚は、可能性の空間を半分に切り捨てる「はい」か「いいえ」の質問をする、20の質問ゲームのようなものです。

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

例えば、この8ビット、つまり奇数番目の位置すべてに対してパリティチェックを行うとしましょう。

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.

これらの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 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.

ここでは、1番目の位置を選びましょう。

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

したがって、示されている例では、これらの8ビットのパリティは現在奇数です。

字幕リスト動画再生

ハム符号とは？誤り訂正の起源 (But what are Hamming codes? The origin of error correction)

specific

assume

matter

flip