Error Correction Codes

Modern computers represent information digitally using 0s and 1s. One major advantage of digital representations is that they are much more resistant to noise than analog representations. A digital circuit does not need to distinguish between every possible voltage—it only needs to decide whether a signal represents a 0 or a 1.

However, digital systems are not immune to errors. The underlying circuits that implement digital logic are still physical, analog systems. Noise, timing violations, radiation, unreliable communication channels, and many other effects can cause a transmitted or stored bit to change.

For example, imagine transmitting a bit wirelessly. The receiver does not literally receive a 0 or 1; it receives an electromagnetic signal and must determine which digital value that signal represents. Noise can distort the signal enough that a transmitted 0 is interpreted as a 1, or vice versa.

For this reason, communication and storage systems often use error-detecting and error-correcting codes.

Example: Adding Redundancy

The basic idea is simple: instead of transmitting only the information we care about, we encode it into a larger number of bits by adding redundancy.

Suppose we want to transmit 1'b1. The simplest possible error-correcting code is the repetition code. Instead of sending one bit, we could send three copies: 3'b111.

Now suppose one bit is corrupted during transmission: 111 → 110. The receiver can see that something went wrong. More importantly, it can recover the original information by taking a majority vote: two bits say 1, one bit says 0, so the message is decoded as 1.

This code can therefore correct any single-bit error. However, suppose two bits are corrupted: 111 → 100. The majority vote now produces 0, so the receiver incorrectly decodes the message.

This illustrates one of the fundamental tradeoffs in error-correcting codes: how much redundancy are we willing to add in exchange for how much protection against errors? And remember, every bit that you send that isn't encoding data means it takes more bits to transmit a certain message. And sending bits does cost oney, time, bandwidth, silicon, etc... So there's a very real tension between sending a lot of data and sending less data robustly. Doing so with "dumb" solutions like the repetition code above is therefore very costly and engineers have for decades spent ways coming up with solving this task more intelligently.

The repetition code above sends three physical bits for every one bit of useful information. We can do much better. Different codes provide different guarantees. For example, a code might:

• detect errors without being able to determine which bit is wrong,
• detect and correct a single-bit error,
• correct multiple errors.

These ideas appear everywhere in computer systems: communication links, networking, SSDs, DRAM/ECC memory, storage devices, and even inside processors and FPGAs. They also extend to quantum computing, where quantum error-correcting codes protect fragile quantum information. The details are quite different—we cannot simply copy an unknown quantum state—but many of the same coding ideas, such as redundancy, parity checks, and syndromes, reappear.

In this exercise, we will explore two classical error-control techniques:

1. Parity checking — detects an odd number of bit flips, but cannot correct them.
2. Hamming codes — use multiple carefully chosen parity bits to determine which bit was corrupted and correct a single-bit error.

Parity Check Code

One of the simplest error-checking techniques is the addition of a parity bit to a message. Before communicating, the transmitter and receiver agree to use either even parity or odd parity. This means both devices expect each message to contain either an even or odd number of 1s. The transmitter adds a parity bit to the message and chooses its value so that this condition is satisfied.

For example:

• With even parity, if we want to send 'b1111001, the parity bit is 1, producing 'b11110011.
• With odd parity, if we want to send 'b1100001, the parity bit is 0, producing 'b11000010.

Important: A parity bit can tell us that an odd number of bits changed, but it cannot tell us which bit changed. Therefore, parity alone detects errors but does not correct them.

You'll write logic to check the parity of these messages by completing the parity_checker module below using strictly combinational logic.

The module outputs a single bit parity:

• parity = 1 if data has even parity
• parity = 0 if data has odd parity

Since parity checking is used with many different message widths, we'll make the module parameterized. Add a parameter WIDTH that determines the width of the data input and defaults to 8. The parity output remains one bit regardless of WIDTH.

Loading...

Hamming Codes

The parity bit solution above is helpful, but is very often not enough. More bits can be used to be more robust. Another downside of the parity approach above is, if we do see a mismatch in parity when checking the message, all we know is that an error happened...we can't figure out what that error was....so we'll have to re-request for the message to be sent again wasting precious bandwidth. There are better ways to do things though...ways that can let us know an error happend and what the error was. One of these approaches is a Hamming Code.

Who doesn't love 3Blue1Brown? The guy's voice and the weird smiling Greek letters are a perfect escape in these trying times. Fortunately for us, he has an excellent visual explanation of exactly how Hamming codes work. Watch these videos before continuing:

• 3Blue1Brown — Hamming codes, part 1
• 3Blue1Brown — Hamming codes, part 2

The key idea is that instead of having one parity bit check the entire message, we use several parity bits, with each parity bit checking a different, overlapping subset of the message.

When a bit is corrupted, multiple parity checks may fail. The pattern of failed checks forms a binary number called the syndrome. The clever part is that the syndrome directly tells us which bit is wrong.

For example, consider a Hamming(7,4) code. Four data bits are encoded into seven transmitted bits:

[p1, p2, d1, p4, d2, d3, d4]

The parity bits occupy positions that are powers of two (1, 2, and 4), while the data bits occupy the remaining positions (3, 5, 6, and 7)...we're using 1-indexing here, which might feel unnnatural but makes things easier below!

Each parity bit checks the parity of all bits (including the parity bit itself) whose binary index contains a 1 in a particular place:

• p1 checks parity of bits with a 1 in the 1's place of their index (positions 1, 3, 5, 7)
• p2 checks parity of bits with a 1 in the 2's place of their index (positions 2, 3, 6, 7)
• p4 checks parity of bits with a 1 in the 4's place of their index (positions 4, 5, 6, 7)

Each parity bit is chosen so that its group has even parity. This is subtle because it means when calculating the value of a parity bit in encoding the message, you only use the appropriate data bits.

As an example, suppose a message is sent using Hamming(7,4) and value at position 6 gets corrupted during transmission. The receiver will see that the parity checks associated with p2 and p4 fail, while the p1 parity check succeeds. The resulting syndrome is 3'b110 = 6, which tells us directly that the value at position 6 is corrupted. We can correct the received message simply by flipping bit 6.

Why this works: Each bit position has a unique binary index. The parity checks that fail encode exactly that index, allowing the decoder to locate the corrupted bit.

So for example, let's say we want to send the message 4'b1110. The message would first get built up with:

{p1, p2, 0, p4, 1, 1, 1}

Calculating the parity bits then leads to:

{0, 0, 0, 1, 1, 1, 1}

The message gets sent and never gets messed with in transit. The result is the following coming in:

{0, 0, 0, 1, 1, 1, 1}

The parity checks yield:

• p1 = 0^0^1^1 = 0
• p2 0^0^1^1 = 0
• p4 = 1^1^1^1 = 0

All three are 0 so no errors!

But what if the second bit of the message (the one carrying p2) gets borked in transit? The message received is:

{0, 1, 0, 1, 1, 1, 1}

• p1 = 0^0^1^1 = 0
• p2 1^0^1^1 = 1
• p4 = 1^1^1^1 = 0

So the wrong bit is at 3'b010 or 2!!! which is p2!!! so we know that was flipped so we flip it back. Bingo Bango Bongo, the whole thing works!

Exercise 2 — Hamming Encoder

Implement a Hamming(7,4) encoder. Your encoder should accept the four original data bits and generate the complete 7-bit Hamming codeword, including the appropriate parity bits. Your implementation should use strictly combinational logic. Remember, computing the parity bits for even parity only involves the data bits.

module hamming_encoder( input wire [3:0] data_in, output logic [6:0] codeword ); // your code here endmodule

Loading...

Exercise 3 — Hamming Decoder

Now implement the receiver. Your decoder should:

1. Compute the syndrome from the received Hamming codeword.
2. Use the syndrome to determine whether a single-bit error occurred and, if so, which bit was corrupted.
3. Flip the corrupted bit.
4. Extract the original four data bits.

Your implementation should use strictly combinational logic.

Because this algorithm is best thought out as an ordered number of steps, we strongly encourage you to try and encode this behavior using one single always_comb block rather than separate assign blocks. Just because the decoding steps can be thought of as "sequential" doesn't mean they have to be implemented using "sequential logic."

You will need to explain to a staff member what your design requires in terms of LUT count so while designing try to think of what is needed (how many bits got into each decision in your algorithm) since that can help you in designing this!

module hamming_decoder( input wire [6:0] codeword, output logic [3:0] data_out ); // your code here endmodule

Loading...

The design you made above for the Hamming Encode and Decoder are both combinational-only circuits. With this in mind, think about how this circuit would actually get turned into LookUp Tables (LUTs) discussed in class. In particular, both modules should be able to be synthesized using only LUT-4s. Sketch out both modules. Start with the encoder, which is easier. Dont' worry about the "program" or truth table for each LUT, we're primarily concerned with the connections

Checkoff 3: Hamming Codes (only a TA or Joe can do this checkoff):
For checkoff 3, walk a TA through your Hamming encoder and decoder. Be ready to explain how the syndrome identifies the corrupted bit, and what happens if two bits get flipped.

You should also be ready to explain how your code synthesizes onto an FPGA using LUT-4 primitives: how many LUT-4s are needed at minimum, and what the depth of your circuit is. Please have the circuits for the Hamming Encoder and Decoder drawn with LUT-4s BEFORE you request the checkoff.

Again, only a TA (Heba, Yeabsira, Subhi, Nerissa, Keilee) or Joe can do this checkoff (it's gonna be hard — study the lecture about LUTs).

Loading...

Something to Think About

Notice how different this is from the repetition code. The 3-bit repetition code requires 3 transmitted bits to protect 1 data bit. Hamming(7,4) protects 4 data bits using only 7 transmitted bits.

For larger Hamming codes, the overhead becomes even smaller. For example, Hamming(15,11) protects 11 data bits using only 4 additional parity bits.