Name: Nhưng mã Hamming là gì? Nguồn gốc của sửa lỗi (But what are Hamming codes? The origin of error correction)
Uploaded: 2026-01-07T04:47:42.000Z
Duration: 20 min 5 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

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?

Bạn đã bao giờ tự hỏi làm thế nào mà một chiếc CD hoặc DVD bị trầy xước vẫn có thể phát lại nội dung lưu trữ của nó chưa?

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

Vết trầy xước thực sự ảnh hưởng đến các ones and zeros trên đĩa, vì vậy nó đọc dữ liệu khác với những gì đã được lưu trữ.

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.

Nhưng trừ khi nó bị trầy xước quá nặng, các bits mà nó đọc được sẽ được giải mã thành chính xác tệp giống như tệp đã được mã hóa lên đó, một bản sao bit-by-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.

Bất chấp tất cả những lỗi đó, có rất nhiều sự khéo léo về toán học cho phép chúng ta lưu trữ dữ liệu và quan trọng không kém là truyền dữ liệu theo cách có khả năng chống lỗi.

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

Thực ra, không cần quá nhiều sự khéo léo để nghĩ ra một cách làm điều này.

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

Bất kỳ tệp nào, dù là video, âm thanh, văn bản, mã code, hình ảnh, hay bất cứ thứ gì, cuối cùng cũng chỉ là một chuỗi các ones and zeros.

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

Và một chiến lược đơn giản để sửa bất kỳ bit nào bị lật là lưu trữ ba bản sao của mỗi 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.

Sau đó, máy đọc tệp này có thể so sánh ba bản sao này và luôn lấy hai bản tốt nhất trong ba bản khi có sự khác biệt.

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

Nhưng điều đó có nghĩa là sử dụng hai phần ba dung lượng của bạn cho 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.

Và ngay cả khi đó, với tất cả dung lượng bị hy sinh, cũng không có gì đảm bảo chắc chắn về những gì xảy ra nếu nhiều hơn một bit bị lật.

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.

Câu hỏi thú vị hơn nhiều là làm thế nào để có thể sửa lỗi, trong khi vẫn hy sinh ít dung lượng nhất có thể.

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.

Ví dụ, sử dụng phương pháp bạn sẽ tìm hiểu trong video này, bạn có thể lưu trữ dữ liệu của mình trong các khối 256 bit, trong đó mỗi khối sử dụng 9 bit, 9 bit này đóng vai trò như một dạng redundancy.

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

Và 247 bit còn lại có thể mang bất kỳ thông điệp hoặc dữ liệu có ý nghĩa nào bạn muốn.

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

Và ngay cả khi có bất kỳ bit nào bị lật ở đây, chỉ cần nhìn vào khối này và không gì khác, máy sẽ có thể xác định rằng có lỗi và, và

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

chính xác là nó ở đâu, để nó biết cách sửa lỗi.

Và thành thật mà nói, điều đó giống như phép thuật.

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.

Và đối với phương pháp cụ thể này, nếu hai bit bị lật, máy ít nhất sẽ có thể phát hiện ra rằng có hai lỗi, mặc dù nó sẽ không biết cách sửa chúng.

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

Chúng ta sẽ nói thêm một chút về cách phương pháp này mở rộng cho các khối có kích thước khác nhau.

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

Các phương pháp cho phép bạn sửa lỗi như thế này được gọi, khá hợp lý, là 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.

Trong phần lớn thế kỷ trước, lĩnh vực này là nguồn tài nguyên phong phú cho các phép toán sâu sắc đáng ngạc nhiên, được tích hợp vào các thiết bị chúng ta sử dụng hàng ngày.

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

Mục tiêu ở đây là mang đến cho bạn sự hiểu biết sâu sắc về một trong những ví dụ sớm nhất được gọi là 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

Và nhân tiện, cách tôi suy nghĩ về cấu trúc của video này là ít giải thích trực tiếp nhất có thể, và

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

thiên về việc khuyến khích bạn tự mình phát minh ra nó với một chút hướng dẫn nhẹ nhàng ở đây và đó.

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

Vì vậy, khi bạn cảm thấy mình đã thấy nó đi đến đâu đó, hãy dành khoảnh khắc đó để tạm dừng.

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

Chủ động dự đoán xem phương pháp này sẽ là gì trước khi tôi nói với bạn.

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.

Ngoài ra, nếu bạn muốn hiểu sâu đến cấp độ phần cứng, Ben Eater đã làm một video kết hợp với video này để chỉ cho bạn cách thực sự triển khai hamming codes trên breadboards, điều này cực kỳ thỏa mãn.

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

Bây giờ, bạn nên biết rằng hamming codes không được sử dụng rộng rãi như các mã hiện đại hơn như thuật toán 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.

Nhưng có một sự kỳ diệu nhất định trong sự tương phản giữa việc nhiệm vụ này có vẻ khó khăn như thế nào lúc ban đầu và việc nó có vẻ hoàn toàn hợp lý như thế nào khi bạn tìm hiểu về 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.

Nguyên tắc cơ bản của việc sửa lỗi là trong một không gian rộng lớn của tất cả các thông điệp có thể có, chỉ một tập hợp con nhất định mới được coi là thông điệp hợp lệ.

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

Như một phép loại suy, hãy nghĩ về các từ được đánh vần đúng so với các từ đánh vần sai.

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.

Bất cứ khi nào một thông điệp hợp lệ bị thay đổi, người nhận sẽ chịu trách nhiệm sửa lại những gì họ thấy về hàng xóm hợp lệ gần nhất, giống như bạn có thể làm với lỗi đánh máy.

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

Tuy nhiên, việc đưa ra một thuật toán cụ thể để phân loại các thông điệp như thế này một cách hiệu quả đòi hỏi một sự khéo léo nhất định.

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

Câu chuyện bắt đầu vào những năm 1940, khi một Richard Hamming trẻ tuổi đang làm việc cho Bell Labs, và

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

một phần công việc của ông liên quan đến việc sử dụng một chiếc máy tính thẻ đục rất lớn, đắt tiền mà ông chỉ có quyền truy cập hạn chế.

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

Và các chương trình mà ông liên tục chạy trên đó liên tục gặp lỗi vì thỉnh thoảng, một bit lại bị đọc sai.

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

Sự thất vọng là cái nôi của sự sáng tạo, ông đã quá chán nản đến nỗi đã phát minh ra mã sửa lỗi đầu tiên trên thế giới.

There are many different ways to frame hamming codes, but

Có nhiều cách khác nhau để trình bày hamming codes, nhưng

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

trước tiên, chúng ta sẽ đi qua nó theo cách mà chính Hamming đã suy nghĩ về chúng.

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

Hãy sử dụng một ví dụ đơn giản, nhưng không quá đơn giản.

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

Chúng ta sẽ đánh số các vị trí của các bits này từ 0 đến 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.

Dữ liệu thực tế mà chúng ta muốn lưu trữ chỉ chiếm 12 bits, trong khi bốn vị trí sẽ được dành riêng cho một dạng redundancy.

The word redundant here doesn't simply mean copyright.

Từ redundant ở đây không chỉ đơn giản có nghĩa là sao chép.

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

Xét cho cùng, bốn bits đó không đủ chỗ để chúng ta sao chép dữ liệu một cách mù quáng.

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

Thay vào đó, chúng sẽ cần một dạng redundancy tinh tế và thông minh hơn nhiều, không thêm bất kỳ thông tin mới nào, mà là

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

Bạn có thể mong đợi bốn bits đặc biệt này được đóng gói gọn gàng với nhau, có lẽ ở cuối hoặc một cái gì đó tương tự.

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.

Nhưng như bạn sẽ thấy, việc đặt chúng ở các vị trí là lũy thừa của hai cho phép một điều gì đó thực sự thanh lịch vào cuối.

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

Nó cũng có thể cho bạn một gợi ý nhỏ về cách điều này mở rộng cho các khối lớn hơn.

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

Ngoài ra, về mặt kỹ thuật, nó chỉ còn 11 bits dữ liệu.

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

Bạn sẽ thấy có một chút khác biệt nhỏ về những gì diễn ra ở vị trí số không.

Nhưng tạm thời đừng lo lắng về điều đó.

Like any error correction algorithm, this will involve two.

Giống như bất kỳ thuật toán sửa lỗi nào, cái này sẽ liên quan đến hai.

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

Một bên gửi chịu trách nhiệm thiết lập bốn bit đặc biệt này, và

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

sau đó là một bên nhận chịu trách nhiệm thực hiện một loại kiểm tra và sau đó sửa lỗi.

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

Tất nhiên, các từ bên gửi và bên nhận thực sự đề cập đến máy móc hoặc phần mềm đang thực hiện tất cả các kiểm tra.

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

Và ý tưởng về một thông điệp được hiểu rất rộng để bao gồm những thứ như lưu trữ.

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.

Xét cho cùng, lưu trữ dữ liệu cũng giống như gửi một thông điệp từ quá khứ đến tương lai, thay vì từ nơi này đến nơi khác.

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.

Nhưng trước khi đi sâu vào, chúng ta cần nói về một ý tưởng liên quan đã nảy ra trong đầu Hamming vào thời điểm ông ấy khám phá ra nó.

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

Một phương pháp cho phép bạn phát hiện bất kỳ lỗi bit đơn lẻ nào, nhưng

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

không sửa chúng, được biết đến trong ngành là kiểm tra chẵn lẻ.

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

Đối với kiểm tra chẵn lẻ, chúng ta chỉ tách ra một bit duy nhất mà bên gửi chịu trách nhiệm điều chỉnh, và

phần còn lại thì tự do mang thông điệp.

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

Nhiệm vụ duy nhất của bit đặc biệt này là đảm bảo tổng số bit 1 trong thông điệp là một số chẵn.

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

Vì vậy, ví dụ, ngay bây giờ, tổng số bit 1 đó là bảy.

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

Vì vậy, bên gửi cần thay đổi bit đặc biệt đó thành một, làm cho số lượng trở nên chẵn.

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

Nhưng nếu khối ban đầu đã bắt đầu với số lượng bit 1 là chẵn, và

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

thì bit đặc biệt này sẽ được giữ ở mức không.

This is pretty simple, deceptively simple.

Điều này khá đơn giản, đơn giản đến mức khó tin.

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.

Nhưng đó là một cách vô cùng tinh tế để chắt lọc ý tưởng về sự thay đổi ở bất kỳ đâu trong thông điệp để được phản ánh trong một bit thông tin duy nhất.

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.

Lưu ý nếu bất kỳ bit nào của thông điệp này bị đảo ngược từ 0 lên 1 hoặc từ 1 xuống 0, nó sẽ làm thay đổi tổng số bit 1 từ chẵn thành lẻ.

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.

Vì vậy, nếu bạn là người nhận, bạn nhìn vào thông điệp này và thấy một số lượng bit 1 là lẻ, bạn có thể chắc chắn rằng đã có lỗi xảy ra, ngay cả khi bạn không biết nó ở đâu.

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

Theo thuật ngữ chuyên ngành, việc một nhóm bit có số lượng bit 1 là chẵn hay lẻ được gọi là 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.

Bạn cũng có thể sử dụng các con số và nói rằng parity là 0 hoặc 1, điều này thường hữu ích hơn khi bạn bắt đầu thực hiện các phép toán với ý tưởng này.

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

Và bit đặc biệt mà người gửi sử dụng để kiểm soát parity được gọi là parity.

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

Và thực tế, nếu người nhận thấy parity là lẻ, điều đó không nhất thiết có nghĩa là chỉ có một lỗi.

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

Có thể có ba lỗi hoặc năm lỗi hoặc bất kỳ số lẻ nào khác, nhưng

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

họ biết chắc chắn rằng nó không phải là số không.

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.

Mặt khác, nếu có hai lỗi hoặc bất kỳ số lượng lỗi chẵn nào, tổng số bit 1 cuối cùng đó vẫn sẽ là số chẵn.

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

Vì vậy, người nhận không thể hoàn toàn tin tưởng rằng một số lượng chẵn nhất thiết có nghĩa là thông điệp không có lỗi.

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

Bạn có thể phàn nàn rằng một thông điệp bị hỏng chỉ bởi hai lần lật bit là khá yếu, và

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.

Tuy nhiên, hãy nhớ rằng, không có phương pháp nào để phát hiện hoặc sửa lỗi có thể cho bạn sự tự tin 100% rằng thông điệp bạn nhận được là thông điệp mà người gửi mong muốn.

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

Xét cho cùng, đủ tiếng ồn ngẫu nhiên luôn có thể làm thay đổi một thông điệp hợp lệ thành một thông điệp hợp lệ khác chỉ do may mắn thuần túy.

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.

Thay vào đó, mục tiêu là đưa ra một sơ đồ mạnh mẽ lên đến một số lỗi tối đa nhất định, hoặc có thể giảm xác suất dương tính giả như thế này.

Parity checks on their own are pretty weak.

Bản thân các kiểm tra parity khá yếu.

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.

Nhưng bằng cách chắt lọc ý tưởng về sự thay đổi trên toàn bộ thông điệp xuống còn một bit duy nhất, chúng mang lại cho chúng ta một khối xây dựng mạnh mẽ cho các sơ đồ phức tạp hơn.

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.

Ví dụ, khi Hamming tìm cách xác định lỗi xảy ra ở đâu, chứ không chỉ là lỗi đã xảy ra, phát hiện quan trọng của ông là nếu bạn áp dụng một số kiểm tra parity không phải cho toàn bộ thông điệp mà cho các tập hợp con được chọn lọc cẩn thận, bạn có thể đặt r

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.

Cảm giác chung hơi giống như chơi trò 20 câu hỏi, đặt ra các câu hỏi có hoặc không để chia đôi không gian các khả năng.

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

Ví dụ, giả sử chúng ta thực hiện kiểm tra parity chỉ trên tám bit này, tất cả các vị trí lẻ.

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.

Sau đó, nếu phát hiện lỗi, nó sẽ cung cấp cho người nhận thêm một chút thông tin về vị trí cụ thể của lỗi, đó là nó nằm ở vị trí lẻ.

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.

Nếu không phát hiện lỗi nào trong số tám bit đó, điều đó có nghĩa là không có lỗi nào cả, hoặc lỗi nằm ở các vị trí chẵn.

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

Bạn có thể nghĩ rằng việc giới hạn kiểm tra parity cho một nửa số bit sẽ làm giảm hiệu quả của nó, nhưng

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.

khi được thực hiện cùng với các kiểm tra được lựa chọn tốt khác, nó lại mang lại cho chúng ta một thứ mạnh mẽ hơn nhiều để thực sự thiết lập kiểm tra parity đó.

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

Hãy nhớ rằng, điều này đòi hỏi phải dành riêng một bit đặc biệt có quyền kiểm soát parity của toàn bộ nhóm đó.

Here, let's just choose position number one.

Ở đây, chúng ta hãy chọn vị trí số một.

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

Vì vậy, đối với ví dụ được hiển thị, parity của tám bit này hiện đang là lẻ.

Subtitles ListPlay Video

Nhưng mã Hamming là gì? Nguồn gốc của sửa lỗi (But what are Hamming codes? The origin of error correction)

specific

assume

matter

flip