P11.31.1 An RS Parity Generator for 10-Bit Symbols

MediumImplementIcarus Verilog · serverReview the topic

Twenty transcoded blocks are 514 symbols of 10 bits. Work out the 14 or 30 parity symbols that turn them into a Reed-Solomon codeword.

Hardware context: An Ethernet MAC and physical coding sublayer: frame builder and checker, reconciliation sublayer and block encoder. Build, check and pace Ethernet frames, and code them for the physical layer as IEEE 802.3 specifies.

rs_parity gets a message of 514 symbols and returns its parity symbols, in sending order.

A symbol is ten bits and stands for an element of GF(2^10). The field polynomial is x^10 + x^3 + 1.

The generator g(x) has 2t roots: alpha^0, alpha^1, up to alpha^(2t-1). Here alpha is the element x, the value 2.

With kp4 = 0 the code is RS(528,514) and 2t is 14. With kp4 = 1 it is RS(544,514) and 2t is 30.

The parity is the remainder of x^(2t) · m(x) divided by g(x). The first symbol sent is the highest power of x.

Here m(x) is the message alone. Equation 91-2 writes m(x) with the x^(2t) already in it.

Three things are course choices. The message is one 5,140-bit vector whose bit 0 is sent first.

One function serves both codes, with kp4 as the switch. And unused result bits are 0.

The lesson shows the encoder only as tables of results. Its readable models hold lanes and lock.

P10.11 has a readable Reed-Solomon model. You may port it: the work is to fit it to Clause 91 and check it against the annex.

Calling the library by name is refused, so the code must be in your answer.

Build g(x) once per call, not once per symbol. The simulator stops a run after 12 seconds.

Signals in the Timeline

SignalWidthRole
test_number8input of each check
Full specification
Signature (keep it)
function automatic [299:0] rs_parity(input [5139:0] msg, input bit kp4);
ItemRule
msga course choice of layout: symbol s is bits 10s to 10s + 9, and bit 0 is sent first. Symbol 0 is m(513), the first one into the encoder
Bits of a symbolbit i of a symbol is the coefficient of alpha^i. Bit 0 is sent first (91.5.2.7)
FieldGF(2^10) with x^10 + x^3 + 1. So alpha^10 = alpha^3 + 1, and adding is XOR
g(x)the product of (x - alpha^j) for j = 0 to 2t - 1 (Equation 91-1). Its top coefficient is 1
Paritythe remainder of the division by g(x), with all delay elements at zero before each message (Figure 91-5)
Resultparity symbol p(2t-1) in bits 9:0, then p(2t-2), down to p(0). That is the sending order
kp4 = 014 parity symbols in bits 139:0. Bits 299:140 are 0, a course choice
kp4 = 130 parity symbols in bits 299:0

Two hidden or visible tests use the codewords of Annex 91A of IEEE Std 802.3-2022. Their parity is the annex's own.

Examples

Example 1

Only the Last Symbol Is 1, RS(528,514)
Input
symbol 513 is 1; `kp4` = 0
Output
first_parity_symbol = 904, second_parity_symbol = 6, parity_symbol_13 = 432, xor_of_all_32_bit_slices = 0x6cd4460

m(x) is 1, so the parity is x^14 mod g(x): the coefficients of g(x) below the top one. The first sent is g13, the last g0.

Example 2

Only the Last Symbol Is 1, RS(544,514)
Input
the same message; `kp4` = 1
Output
first_parity_symbol = 575, second_parity_symbol = 552, parity_symbol_13 = 720, xor_of_all_32_bit_slices = 0x58387126

Now g(x) has 30 roots. The first parity symbol is g29, and parity symbol 13 is g16.

Example 3

The Codeword of Annex 91A, RS(528,514)
Input
the 20 transcoded blocks of the annex; `kp4` = 0
Output
first_parity_symbol = 183, second_parity_symbol = 924, parity_symbol_13 = 656, xor_of_all_32_bit_slices = 0x71ccf223

The annex lists the parity in hex, the first bit sent leftmost. Its first ten bits, read lowest bit first, are 183.

Constraints and Contract

  • Keep the name and the arguments of rs_parity.
  • A call must not depend on the calls before it.
  • Your answer must hold its own multiplier and division. You may add helper functions.
  • Off limits: the names lib, rng, tb, root, names that begin with fx_ and the modules of the bench.

Hints

Hint 1

Start with the multiplier. Test it by hand: alpha^9 times alpha is alpha^3 + 1, the value 9.

Hint 2

Build g(x) one root at a time: multiply the polynomial so far by (x + alpha^r).

Hint 3

One step of the register: the feedback symbol is the input XOR the top delay element.

Hint 4

The top delay element holds the parity symbol that is sent first.

Hint 5

Too slow? A multiplier of ten shift-and-XOR steps is fast enough. One that handles 100 single bits per product is not.

What the grader checks: The fixture checks 11 fixed messages against an independent JavaScript model: 12 calls of rs_parity in all. Two messages are the codewords of Annex 91A of IEEE Std 802.3-2022, with the annex's own parity as the expected result. The model also gives the coefficients of Table 91-1. One test encodes two messages in a row, with the other code first. No random messages are run, to keep the run short. The one-vector layout, the kp4 switch and the zero upper bits are course choices. Decoding, the alignment markers and the symbol distribution are not graded.

11 checks on Icarus Verilog · server. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain your source only; samples require the simulation service. A passing result establishes the tested cases, not a proof for all possible inputs.

See all 1 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

Only the Last Symbol Is 1, RS(528,514)

Input
symbol 513 is 1; `kp4` = 0
Expected output
first_parity_symbol = 904, second_parity_symbol = 6, parity_symbol_13 = 432, xor_of_all_32_bit_slices = 0x6cd4460

m(x) is 1, so the parity is x^14 mod g(x): the coefficients of g(x) below the top one. The first sent is g13, the last g0.

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

Icarus Verilog · server