P10.11.2 Correct One Symbol

HardImplementIcarus · browser samples / server checksReview the topic

Write the decoder of a small Reed-Solomon code. Find one wrong symbol from two syndromes, repair it, and say when no single error fits.

Hardware context: The digital blocks of a serializer/deserializer: line encoder and decoder, scrambler, CRC and error-correcting code. Keep the line balanced and busy, and detect or correct the errors a fast serial link makes.

A code word has 15 symbols of four bits. Thirteen carry data and two are check symbols. The code can correct one wrong symbol, whatever bits inside it are wrong.

Write rs_fix(c). Compute the two syndromes of the received word. If both are zero, the word is clean. If both are non-zero, the decoder assumes one symbol is wrong: find it, repair it and report "corrected".

If exactly one syndrome is zero, no single error fits. Leave the word alone and report "not correctable".

The field arithmetic is given: gf_mul, gf_exp and gf_log. The tests hit every symbol with every error value, including the two check symbols.

Signals in the Timeline

SignalWidthRole
test_number8input of each check
Full specification
Signature (keep it), and the helpers you are given
function automatic [61:0] rs_fix(input [59:0] c);          // returns {status[1:0], word[59:0]}
function automatic [3:0] gf_mul(input [3:0] a, input [3:0] b);   // product in GF(16), x^4 + x + 1
function automatic [3:0] gf_exp(input int i);                    // alpha^i, alpha = 2, any integer i
function automatic int gf_log(input [3:0] a);                    // i with alpha^i = a, 0 to 14; -1 for a = 0
ItemDefinition
Symbol ic[4*i+3 : 4*i], for i = 0 to 14. Addition of symbols is XOR.
Syndrome s0The XOR of all 15 symbols
Syndrome s1The XOR of symbol i times alpha^i, over all i
A valid words0 = 0 and s1 = 0
One error e at symbol ps0 = e and s1 = e times alpha^p
Syndromesstatusword returned
Both zero0 (clean)The input
Both non-zero1 (corrected)The input with s0 XORed into symbol p, where alpha^p = s1 / s0
Exactly one zero2 (not correctable)The input

With two wrong symbols the decoder may still report "corrected" and return a wrong valid word. That is the limit of this code, and the tests expect exactly that behaviour.

Examples

Example 1

A Clean Word
Input
a valid code word
Output
word = 0x5aebd30c65ece61, status = clean (0)

Both syndromes are zero, so the status is 0 and the word comes back unchanged.

Example 2

All Four Bits of Symbol 5 Wrong
Input
the same word with symbol 5 XOR Fh
Output
word = 0x5aebd30c65ece61, status = corrected (1)

s0 is Fh, the error value. s1 / s0 is alpha^5, so symbol 5 is repaired. Four wrong bits count as one wrong symbol.

Example 3

The Same Error Value in Symbols 0 and 1
Input
the same word with symbols 0 and 1 XOR 1h
Output
word = 0x5aebd30c65ece70, status = not correctable (2)

The two errors cancel in s0 but not in s1. One zero syndrome fits no single error, so the status is 2.

Constraints and Contract

  • Keep the function name, the argument and the 62-bit result.
  • Use the given field helpers. You may add helper functions of your own.
  • Symbol positions run from 0 to 14.

Hints

Hint 1

Write the two syndromes first and check that they are zero for the clean example.

Hint 2

For one error, s0 is the error value itself. Dividing s1 by s0 leaves a power of alpha. Which helper turns a power back into its exponent?

Hint 3

A difference of two logarithms can be negative. The position must still land between 0 and 14.

What the grader checks: The fixture checks 450 single-symbol errors, 40 clean words and 300 double errors against a decoder model for this one code. It does not test other code sizes or a hardware implementation.

7 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

A Clean Word

Input
a valid code word
Expected output
word = 0x5aebd30c65ece61, status = clean (0)

Both syndromes are zero, so the status is 0 and the word comes back unchanged.

Run samples executes all 3 public checks. Check all tests runs 7 checks on the server.

Icarus · browser samples / server checks