Hello all,

I can't seem to wrap my mind around my assignment involving error correcting code. Hopefully we can take steps to gain understanding because my professor has been a bit unhelpful thus far and does not hold office hours

FIRST STEP:

​

1) Create an ECC Generator, at the I/O Controller from the 8-bit Data Vector. The output of the ECC Generator will be the 4-Bit Parity Vector. (working in logicworks).

would this just mean XOR'ing the 8 bits of data followed by additional XOR gates to create the parity bit(s)? we are dealing with even parity, by the way.

 

There isn't enough information given to implement an ECC generator.

Basically you are working with an ECC that is structured as follows:

Each n-bit codword contains (n-k) data bits and k checksum bits. Each of the k checksum bits is the parity of some specific subset of the other bits.

But there are numerous possibilities for how to set up the subsets, and so there are numerous possible ECC codes that can be set up this way. You need information about the specific subsets that are to be used.

One common code, the Hamming code, works basically as follows:

Number the n bit positions 1 through n and express them in binary:

001
010
011
100
101
110
111

If a position only has a single 1 in it, then that is one of the parity bits. If it has more than one 1 in it, then it is a data bit. Each parity bit is the parity taken over all of the data bits that have a 1 in the same position as the parity bit.

But that can't be the code you are using because you have eight data bits and four checksum bits and that doesn't fit the Hamming model. But I can pretty much guess how your ECC is constructed and it is pretty similar.

Please try to find and post the specifics ECC generation requirements you are working against.

 

Problem Statement:
The predominant storage inside a computer systems are on disks drives. SCSI disks are the standard disks in most Unix Workstations from Sun, HP, SGI, and other vendors. They are also the standard disks in Macintoshes and Higher-end Intel PC's, especially network servers. Consider the Wide Ultra4 SCSI which transfers data packets in 16-bit
bursts at 160 MHz with a maximum throughput of 320 MB/sec. The data transfers at higher rates can result in random-noise pulse changes from a 0 to 1 and 1 to a 0. As the speed of processors and electronic communications increases, these parity flips become more prevalent and the inability to detect when these errors occur can be fatal. As a Design Engineer you have been requested to create system for the transmission of these 8-bit packets from an I/O Controller to Memory using Error Correcting Code over 12-bit data bus line. Wide SCSI contains a 68bit bus; however for the sake of simplification we are only concerned with the data bits. The other bits in the SCSI bus are for bus arbitration, synchronization, power management, etc. In this project, we will use even parity.

that is the full problem text. Hope this helps!

 

So it sounds like you have been requested to use what you have learned about the concepts of parity-based error correcting codes to construct a code that will let you correct any 1-bit error using a set of four parity bits that cover different subsets of a set of eight data bits.

So what do you know about how parity-based error correcting codes work and how can you apply that knowledge to this problem?

 

i know that parity bits are used to detect errors in communication/data processing. (an extra bit may be added to a binary code to define its parity, making the total number of 1's either even or odd.)

I know that designing decent code should consider the ratio of parity to data bits as well as the processing time to encode/decode should be minimized. (hence the (12,8) specifications of the assignment i assume..) I know that 4 parity bits enables error correction for 5-11 data bits.

I know im lacking in some aspects... perhaps an "english" explanation of how these parity bits work would help. My textbook is loaded and wordy and hard to comprehend to be quite honest. I feel im just missing a fundamental understanding... why or what these parity bits do, not finding it intuitive at all

 

Okay, let's take it from step 1. You'll see it's actually pretty straight foward.

Let's say I have 4 data bits, ABCD.

Now let's add a single parity bit, E, that forces the overall parity to be even. So now my codeword is

ABCDE

E = XOR(ABCD)

I can detect any single bit error because the parity will not work out. But I have no way to know which of the five bits have the error.

But what if I had a second parity bit that only covered bits AB and itself. Call this parity bit F. Now my codeword is six bits

ABCDEF

E = XOR(ABCD)
F = XOR(AB)

Now let's say that the received codeword has a one bit error (and never forget that the error could be in one of the parity bits).

If it passes the parity test on E, then the error has to be in F because that's the only place where a 1-bit error could occur and let E pass.

If it doesn't pass E then the error is in A,B,C,D, or E. But since there is only a single bit error, F has to be correct.

If the parity check on F passes, then we know that A and B are correct, so the error has to be in C, D, or E. But we don't know which.

If the parity check on F fails, then we know that either A or B is incorrect (remember, we already know that F, itself, is correct). But we don't know which.

d it doesn't pass F, then the error must be in A or B because those are the only two bit positions that would cause it to fail both. But we can't tell which one has the error.

If it doesn't pass E and it does pass F, then the error must be in C, D, or DB because those are the only two bit positions that would cause it to fail both. But we can't tell which one has the error.

But what if we added another bit that covered A and C (as well as itself)? Call this bit G. Now we have

ABCDEFG

E = XOR(ABCD)
F = XOR(AB)
G = XOR(AC)

Now, if we have a one bit error but it passes the parity test on E, we know that the four data bits are correct but we don't know if the error is in F or G. But one of them will pass and the other won't -- the one that doesn't pass is the one with the error. But, to some degree, it doesn't matter whether we can tell which parity bit has the error because we have already determined that what we care about, the data, is correct.

So now let's consider the case if E fails its parity check. That means that the error is in A,B,C,D, or E and it also means that F and G are correct.

We have four possibilities when we check the parities of F and G -- they either pass (P) or they fail (F)

F G
------
P P - Error is not in A or B or in A or C. So it must be in D or E
F P - Error is in A or B and is not in A or C. So it must be in B
P F - Error is not in A or B but it is in A or C. So it must be in C
F F - Error is in A or B and it is in A or C. So it must be in A

What you should notice is that we can identity every possible 1-bit error except an error in D or E. Why can't we determine that? Let's look at our parity generators:

E = XOR(ABCD)
F = XOR(AB)
G = XOR(AC)

Notice that A, B, C each affect at least two of the parity bits, but D only affects one.

What we want is for each data bit to affect a different subset of at least two parity bits. With three parity bits, we can make the following subsets containing at least two members: (EF, EG, FG, EFG). So what if we have bit A affect EF, bit B affect EG, bit C affect FG, and bit D affect EFG? Then our parity generator is

E = XOR(A,B,D)
F = XOR(A,C,D)
G = XOR(B,C,D)

Now go through and assume you receive a pattern that has one bit error in it. Based on whether E, F, and G, pass their parity tests, figure out which bit has the error.

Notice that there are eight possible combinations of pass/fail. But you only have seven bits. That means that there is one pass/fail pattern that you cannot ever see with a single bit error. Which one is it and why?

Once you understand this 4+3 (four data plus three parity) code, you should have no problem seeing how to construct an 8+4 code using the same strategy.

 

very helpful explanation! Here is my attempt using your same lettering system.

8 bits- a,b,c,d,e,f,g,h
4 parity bits - w,x,y,z

w = XOR(a,b,c,h)
x = XOR(a,c,d,e)
y = XOR(b,e,f,h)
z = XOR(f,g,h,d)

as you said, "each data bit to affect a different subset of at least two parity bits. With three parity bits, we can make the following subsets containing at least two members"

am I correct in my logic here??? hoping to finally get this logic diagram going if im on the right path

 

You are very close.

Notice that data bits a and c both affect parity bits w and x (and only w and x).

You can be more systematic by listing the possible groupings of two or more parity bits. There are a total of 11 of them -- 6 involving two parity bits, 4 involving three parity bits, and 1 involving all four. You can pick any eight of them.

Since there are 11 of them, the maximum number of data bits you can have is 11.
Recall that if you had just three parity bits you had 4 patterns. So to protect 5 data bits you need 4 parity bits. Now you see where the statement that "4 parity bits enables error correction for 5 to 11 data bits" comes from.

 

Oh, and here's a little puzzle for you.

How many data bits can two parity bits protect?

Come up with the equations for the two parity bits.

Does the answer make sense?

 

d only affects x & z and e only affects x & y right? not sure I see your point about a and c inparticular.. could be the lack of sleep heh... excuse my obvious cluelessness but what do you mean by your systematic approach? are u referring to picking an input to run through the circuit? ah well, time to rest and get back at it tommorow! thanks!

 

here's my 2nd attempt.

w: XOR(BDEGH)
X: XOR(BCEFH)
Y: XOR(AEFG)
Z: XOR(ABCD)

I believe it follows all of your guidelines. how does it look?

 

here's my 2nd attempt.

w: XOR(BDEGH)
X: XOR(BCEFH)
Y: XOR(AEFG)
Z: XOR(ABCD)

I believe it follows all of your guidelines. how does it look?

after more consideration, I came up with a revised answer.

w: XOR(ABDEG)
X: XOR(ACDFG)
Y: XOR(BCDH)
Z: XOR(EFGH)

I am more confident about this 1!

 

very helpful explanation! Here is my attempt using your same lettering system.

8 bits- a,b,c,d,e,f,g,h
4 parity bits - w,x,y,z

w = XOR(a,b,c,h)
x = XOR(a,c,d,e)
y = XOR(b,e,f,h)
z = XOR(f,g,h,d)

d only affects x & z and e only affects x & y right? not sure I see your point about a and c inparticular

Which parity bits are affected by data bit a?

Which parity bits are affected by data bit c?

Are these two different sets?

If they aren't, then that's my point.

what do you mean by your systematic approach? are u referring to picking an input to run through the circuit?

I don't follow what your second question there is talking about.

But for the first one, let's go back to the case of three parity bits.

With parity bits x,y, and z, how many different sets can be constructed that contain at least two of them?

Well, we can just list them:

{x,y}, {x,z}, {y,z}, {x,y,z}

So we can assign each set to a different data bit. By assigning it, we mean that the data bit will affect the parity of each bit in the set.

So let's assign our data bits, {a,b,c,d} in order:

a affects {x,y},
b affects {x,z},
c affects {y,z},
d affect {x,y,z}.

Now we can reverse this to get the list of bits that affect each of the parity bits

x is affected by {a,b,d},
y is affected by {a,c,d},
z is affected by {b,c,d}.

Each parity bit is simply the XOR of all of the bits that affect it, so

x = XOR(a,b,d),
y = XOR(a,c,d),
z = XOR(b,c,d).

 

after more consideration, I came up with a revised answer.

w: XOR(ABDEG)
X: XOR(ACDFG)
Y: XOR(BCDH)
Z: XOR(EFGH)

I am more confident about this 1!

It's easy enough to check. List the sets of parity bits that are affected by each data bit and then see if they are all different.

One of the most important skills that you need to develop is the ability to check your own work. In most cases, you can figure out a way to verify that your solution is correct (or at least is probably correct).

It's important because "in the real world", someone is going to pay you to solve a problem for you and if they knew what the solution was then they wouldn't need to waste money paying you. You have value because you can come up with a solution but you won't have anyone else around to check your work, so you have to be able to do it yourself.

 

Thanks. To calculate parity bits for 8 bit data, I found in my book that

P1: = XOR of bits(3,5,7,9,11)
P2: = XOR of bits(3,6,7,10,11)
P3: = XOR of bits(5,6,7,12)
p4: = XOR of bits(9,10,11,12)

** p1-p4 parity bits, and bits/parity bits numbered 1-12 from left to right) **

so it is, P1,P2,bit3,P3,bit5,bit6,bit7,P4,bit9,bit10,bit11,bit12

following this bit pattern, we have the correct 12 bit code, correct?
I have created this circuit and I seem to be getting correct output for various inputs..

I Think it is time for step 2 and 3 of the assignment.

2) Construct a 12-bit Data Transmission bus to send the binary data and parity bits over to Memory.​

3) Construct an ECC Detector at Main Memory that corrects for single bit errors. We will use 3 Hex displays, 2 for data and 1 for an error status, for diagnostic purposes:


NOW!, these 12 bits I have generated are what i need to pass through a ECC detector in order to correct for one bit errors, correct? and am i correct in assuming they must be in the exact bit order that i described above? THANKS!

 

Thanks. To calculate parity bits for 8 bit data, I found in my book that

P1: = XOR of bits(3,5,7,9,11)
P2: = XOR of bits(3,6,7,10,11)
P3: = XOR of bits(5,6,7,12)
p4: = XOR of bits(9,10,11,12)

** p1-p4 parity bits, and bits/parity bits numbered 1-12 from left to right) **

so it is, P1,P2,bit3,P3,bit5,bit6,bit7,P4,bit9,bit10,bit11,bit12

This is a truncated Hamming code and is one specific choice of the parity bit sets coupled with a specific ordering of the bits (the ordering serves no purpose except to make understanding how they chose the parity sets easier to understand).

following this bit pattern, we have the correct 12 bit code, correct?

Correct according to what metric? This is probably the code they want you to use since it is the one your text presents (would have been nice to know that much earlier -- remember I asked if a particular ECC had been specified).

I have created this circuit and I seem to be getting correct output for various inputs..

I Think it is time for step 2 and 3 of the assignment.

Probably, but there is absolutely no need to shout by using an oversized font. Just use the default font unless there is a specific and compelling reason to do so. Otherwise you just annoy the people that are trying to help you.

Yes, the bits have to be presented to the ECC detector in an exact order. But that is true of just about any circuit.

 

appologies for the oversized font, not even sure how it happened.

anyways, I have been successful in designing a circuit that ...

1.)takes an 8 bit input and displays 12 bit vector with parity bits in their appropriate positions. This is the "encoder" portion of the assignment.

_________________________________________________________________

I am having some troubles constructing a working "ECC detector" or decoder to check and correct one bit errors. I'm having trouble finding information on this in general. I have a basic idea of what I need to do

- process all 12 bits, once passed the decoder i should have 8 bits that I must XOR with the original 8 bit input. Hence the end of the circuit should look something like 8 , 2-pin XOR gates. 1 pin directly recieving original input and the 2nd pin recieving the other decoded 8 bits. Is my understanding flawed?

 

I am having some troubles constructing a working "ECC detector" or decoder to check and correct one bit errors. I'm having trouble finding information on this in general. I have a basic idea of what I need to do

- process all 12 bits, once passed the decoder i should have 8 bits that I must XOR with the original 8 bit input. Hence the end of the circuit should look something like 8 , 2-pin XOR gates. 1 pin directly recieving original input and the 2nd pin recieving the other decoded 8 bits. Is my understanding flawed?

You can do something like this. Basically your detector circuit should generate an error vector that youi XOR with the received vector. The error vector will have a 1 in any spot that needs to be flipped. You correct the entire 12-bit codeword and then pull out the 8-bit data, or pull out the 8-bit data and only generate the error vector for those eight bits.

To generate the error vector, look up information on Hamming Codes.

 

I have successfully generated a 4 bit error vector corresponding to the position of the error. Now, the finall step of XORing this data with the original input.. How do I XOR a 4 bit data with my original 8 bit input or is there another piece I need in the middle like a line decoder or someting.

these 4 bits only give me the position of the 1 bit error. (1010 means bit #10 has an error.) is the error vector supposed to be 8, 12 bits??? would make more sense since I have to XOR with the original vector.


Almost there!

 

Yes, if you are using the normal method for getting the error position for a Hamming code then you have the error position in the original 12-bit vector. So you need to generate the error vector for the 12-bit codeword.

So what is the name that we use for the common circuit that takes ab N-bit binary input and puts out a 1 on one of 2^N outputs and 0s on all of the others?