P11.29.4 Find and Remove One Burst

MediumImplementIcarus Verilog · serverReview the topic

A burst of wrong bits hit an FEC block. The 32 parity bits can tell you where it is and which bits to flip. Write the decoder that finds it.

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.

fec_decode gets one FEC block of 2,112 bits, as received. It returns the 32 words and a status.

First divide all 2,112 bits by g(x). A remainder of zero means the parity matched: status 0.

If not, look for one burst of up to 11 bits that gives this remainder. A burst runs from its first wrong bit to its last.

There is at most one such burst in a block. Flip its wrong bits and return status 1. It may lie in the words, in the parity, or across both.

If no such burst fits, return the words as received with status 2.

The lesson shows one way to search: error trapping. Any way with the same result is accepted.

Three things are course choices. The bench has taken PN-2112 off already, so rx is the plain block.

This decoder stops at 11 bits. The standard asks for at least 11 (74.7.4.5.1). A burst of 12 or 13 bits must get status 2.

A pattern that would start in front of bit 0 gets status 2, and no bit changes. The block is a shortened codeword: it has no bit there.

And an uncorrected block goes out as it came in. Marking it for the PCS is not part of this problem.

One result is not a choice. A long error can have the remainder of a short burst somewhere else.

Your decoder must then remove that short burst and return status 1. It cannot tell the two cases apart, and no decoder can.

No readable model holds this search. You may reuse your division from P11.29.2.

Signals in the Timeline

SignalWidthRole
test_number8input of each check
Full specification
Signature (keep it)
function automatic [2081:0] fec_decode(input [2111:0] rx);
ItemRule
rxbit 0 was received first. Bits 0 to 2,079 are the 32 words. Bits 2,080 to 2,111 are the parity. PN-2112 is off already (a course choice)
Result, bits 2,079 to 0the 32 words: corrected for status 1, as received for status 0 and 2
Result, bits 2,081 and 2,080the status. 0: the parity matched. 1: one burst was removed. 2: not corrected (these values are a course choice)
g(x)x^32 + x^23 + x^21 + x^11 + x^2 + 1 (Equation 74-1)
Orderthe first bit received is the highest power of x. Bit 2,111 is the term x^0
Parity matchedthe remainder of all 2,112 bits divided by g(x) is zero
Burstfrom its first wrong bit to its last, at most 11 bits. The bits between may be right or wrong
Whereanywhere from bit 0 to bit 2,111. A burst in the parity alone changes no word, and is still status 1
12 bits and morestatus 2 (a course choice: the standard sets 11 as the least a decoder must correct)
In front of bit 0a pattern that would need a wrong bit before bit 0 is no burst of this block: status 2. The standard does not say this. It follows from the shortened code (74.7.1)

Mind the time limit. Keep the remainder in one 32-bit vector and step it with whole-vector operations.

A loop over the 32 stages for every bit of the block is correct too, but it runs about 20 times slower.

Examples

Example 1

A Clean Block
Input
no wrong bit
Output
status = parity matched (0), word_bits_changed = 0, first_changed_bit = 0, fold_of_the_words = 0xfa5d5867

The remainder is zero. The words go out as they came in, with status 0.

Example 2

One Wrong Bit
Input
bit 1,000 is wrong
Output
status = burst removed (1), word_bits_changed = 1, first_changed_bit = 1000, fold_of_the_words = 0xfa5d5867

One bit of the words is flipped back: bit 1,000. The status is 1.

Example 3

A Burst of 11 Wrong Bits
Input
bits 700 to 710 are wrong
Output
status = burst removed (1), word_bits_changed = 11, first_changed_bit = 700, fold_of_the_words = 0xfa5d5867

Eleven bits change, from bit 700 on. That is the longest burst this code is sure to correct.

Constraints and Contract

  • Keep the name and the argument of fec_decode.
  • Do the division yourself: the bench library's CRC model is not allowed here.
  • The simulator here does not accept break. Stop a loop with a done flag in its condition, or with return.
  • A call must not depend on the calls before it.
  • You may add helper functions and module-level tables.
  • Off limits: the names ref_dec, rng, tb, root, names that begin with fx_ and the modules of the bench.

Hints

Hint 1

Start with the samples that have one wrong bit. Where is it, counted from the last bit of the block?

Hint 2

The remainder of a burst in the last 11 bits of the block is the burst itself.

Hint 3

For a burst further up, undo one shift of the division at a time. To divide by x when bit 0 is set, add g(x) first.

Hint 4

Count your steps: the count tells you which bit of the block the lowest bit of the pattern stands for.

What the grader checks: The fixture checks 10 fixed blocks against an independent JavaScript model. They cover the edges: bit 0, the last parity bit and bursts of 11 bits. Two more are a pattern in front of bit 0 and a mis-correction. It then sends 14 random blocks. Thirteen are a codeword plus something the fixture placed, so the right result is known without a decoder. That is nothing, a burst of 2 to 11 bits, or a burst of 12 bits. Or it is parity bits that look like a pattern in front of bit 0. Bursts of every length from 2 to 11 are among them. One more random block carries a long error and is compared with a private decoder. On a full check the random blocks change with every submission. The list is short so that a slow but correct answer stays inside the time limit. PN-2112 is taken off by the bench. The stop at 11 bits and the status values are course choices. Error marking for the PCS, the counters and the FEC lock are not graded here.

16 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 5 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 Block

Input
no wrong bit
Expected output
status = parity matched (0), word_bits_changed = 0, first_changed_bit = 0, fold_of_the_words = 0xfa5d5867

The remainder is zero. The words go out as they came in, with status 0.

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

Icarus Verilog · server