Tác giả giữ toàn bộ bản quyền (All Rights Reserved) — không phải giấy phép mở. Bạn vẫn xem và học miễn phí trên OpenER; muốn tái sử dụng cần xin phép tác giả.
[MUSIC PLAYING] PROFESSOR: Hello and welcome back to our dependability module.
So we have seen that there do exist codes that not only can detect errors, but can also correct them. But the example that we have shown is not a very practical one.
Because it has a lot of overhead. In order to encode what was worked one bit of information, we used three bits. So we had 200% overhead there.
The trick here, and the science, is how to design these codes such that we get the desired coverage with minimal amount of overhead.
And desired coverage here is [INAUDIBLE] that single error detection, single error correction, with double error detection. So having came up with those codes as well.
And here is how it goes. We will start with data bits that are a result of our calculation.
And we are going to interleave parity bits with those data bits to form the code word that you're going to store in the memory.
In this case, there is a particular algorithm how they are being put together. So here is how the interleaving works.
On top of this table here, we have bit positions of the code words that are going to be stored in the memory, one, two, three, four, five, and so on.
And then below that encoded data bits are sitting at particular bit positions. D1 is at position three.
D2 is at position five. D3 is at position six, and so on. And these other bit positions are occupied by the parity bits, P1, P2, P4, P8, P16.
And this is done in a particular way, such that parity bits are essentially always at bit positions that correspond to powers of two.
So these are bit positions that in binary correspond to 1, 10, 100, relatively easy to remember.
But then on the bottom here in this table is shown which data bits are covered by which particular parity bit.
So the first parity bit, P1, covers all positions that have an LSB equal to 1. So all odd bits are covered by the first parity bit.
So if we include the P1 in that position, it is going to also cover itself and produce and even parity.
So essentially, every other bit is included in the first parity. What does it mean included? These are basically inputs in the next [INAUDIBLE] that are generating P1.
P2 covers all bit positions that have the bit that is next to the least significant one equal to 1.
So these are essentially pairs of these pink fields that correspond D1, D3 and 4, and so on.
And then P3 covers groups of 4, and so on. And this can continue indefinitely. But in practice, we generally do this for a block.
So if you have a data word that is eight bits wide, we would add four parity bits to encode it. Let's take a look at an example of how we actually do that.
So we are going to generate these parity bits to create even parity for each group. Let's say that we would like to encode a byte of data.
There are eight bits in this word here. So we are going to create a coded word by placing the data bits where they should be.
And then we leave those spaces for our calculated parity bits. So these parity bits should be placed in their appropriate bit positions.
So the first bit, first parity bit, goes into a bit position one. So let's calculate. And let's go through that example.
So position one is going to be checking bits one, three, five, seven, nine, and 11. So we are going to mark those bits in yellow and count how many ones are there.
One, two, three, four. Therefore, in order to make even parity, the parity bits should be equal to zero.
In position two, there's going to be checking pairs of bit, 2,3, 6,7, 10,11. How many ones are there? There are three.
Therefore, in order to make it even parity, we should make this question mark equal to one. Then we take a look at position four checks, mark up appropriate bits.
We have only one among the yellow bits. Therefore, that should be also equal to one. And finally, for position eight checks, we have the last four bits that participate in that [INAUDIBLE].
There are two ones among them. Therefore, this question mark should be equal to zero. All right, so this is our final code word. It consists of the data word and the parity checks.
But let's don't look at the correct answer. Let's suppose we receive something. And we would like to decode if the word is correct.
And if it is not correct, we would like to correct it. So suppose we receive this. We will map it to appropriate bit positions.
And we'll find out that at bit 01 in the first two bit positions are parity bits. There is another one over here that is a parity bit, P4.
And finally, there is a parity bit P8 at the bit position eight. The rest are the data bits. Let's figure out if the word is correct. So we receive this.
And we're going to run the parity checks. Well, for the first parity check, we are going to figure out all the bits, parity bit and the data bits, that correspond in that check.
The number is even. So it's good. It passes. The second one has the P2 parity as one, two, three, four, five ones.
So it's not good. It's not correct. That one does have an error. Then we are going to check the bit P4.
It has two ones in that check. So that is going to be correct. The check is going to be fine. And finally P8 bit is an error.
Because it has three ones. And then there is a very simple way how we calculated which bit position is the error. And you can work out the algebra.
It's very simple. It's very elegant. This implies that the bit position is equal to the sum of the two parity bits, P2 and P8.
So the error is going to be in the bit position 10. What should we do to fix that? We just go ahead and flip that incorrect bit, turn it into a zero.
Then we decode this to make sure that it is correct. Miraculously all the checks are satisfied. And we have decoded a correct word.
Very well. Now, what should we do if we have to deal with systems that can have more than one bit in error?
So if you look at high end microprocessors, they typically use SECDED codes, single error correction double error detection.
But some of the server processors that are working with more valuable work loads are going to have protection to perform correction on two bits.
So there is a different type of a hamming code that is called double error detection triple error detection, or DECTED. We're not going to go into it.
And there are plenty of references of that.
But generally, when we work with something that is noisier than microprocessors, like sending data over Wi-Fi, or network transmissions, and so on, we are going to see a lot more errors.
And these errors are often going to be bursty. And we're going to see different ways how redundancy is added.
There are generally things that we are going to encounter there, like cyclic error correction, forward error correction, and things like interleaving to break up these patterns and attack them with codes that can cover fewer errors.
But that's way past the content of this course. That is it. This is all what we are going to cover here regarding correction of soft errors.
And that is typically something that we are going to do in the memory. We are going to see a different view of redundancy just after a quick break.
Đăng nhập để đánh giá học liệu này.
Đăng nhập để bình luận — chưa ai bình luận về học liệu này.
Không có khóa học liên quan.