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
| Signal | Width | Role |
|---|---|---|
test_number | 8 | input of each check |
Full specification
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
| Item | Definition |
|---|---|
| Symbol i | c[4*i+3 : 4*i], for i = 0 to 14. Addition of symbols is XOR. |
| Syndrome s0 | The XOR of all 15 symbols |
| Syndrome s1 | The XOR of symbol i times alpha^i, over all i |
| A valid word | s0 = 0 and s1 = 0 |
| One error e at symbol p | s0 = e and s1 = e times alpha^p |
| Syndromes | status | word returned |
|---|---|---|
| Both zero | 0 (clean) | The input |
| Both non-zero | 1 (corrected) | The input with s0 XORed into symbol p, where alpha^p = s1 / s0 |
| Exactly one zero | 2 (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