Finding the error in a parity block

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. How do you find the bit that changed in a parity block?

A Find the row and the column that both fail their parity check. The error is where they cross.

B Find the row that fails and flip any bit in that row.

2. Row 3 and column 5 both fail their parity check. Where is the single-bit error?

A At the one bit where row 3 meets column 5

B In every bit of row 3 and every bit of column 5

3. You have found the changed bit at the intersection. How do you correct it?

A Flip it: change a 0 to a 1, or a 1 to a 0

B Delete the bit and shorten the block

4. Which statement is true?

A A single parity bit can locate a single-bit error, but a parity block cannot.

B A parity block can locate a single-bit error, but a single parity bit can only show that an error happened.

5. Only row 2 fails its parity check. What does that tell you on its own?

A You know exactly which bit changed

B The error is somewhere in row 2, but you do not know which column

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1Row 3 fails, column 5 fails		AThe row and column numbers are swapped. The error is at row 2, column 4, where the failed row and failed column cross.
2Flip bit at row 3, column 5: 1 -> 0		BThe changed bit is at the crossing point of row 3 and column 5
3The row and the column that both fail their parity check cross at the bit that has changed		CA failed row alone does not locate the bit. You also need the failed column, and the changed bit is where they cross.
4A parity block can correct a single-bit error, which a single parity bit cannot		DCorrects a single-bit error once the changed bit has been found
5Only row 2 fails, so the error is the whole of row 2		EError at row 2, column 4 is 0 -> flip it to 1
6Row 2 and column 4 fail, so the error is at row 4, column 2		FRow 2 odd + column 4 odd -> error at row 2, column 4

Definitions

failed row and column

Fill in the Blanks

Complete each line of code by filling in the missing parts.

IF rowSum ___ 2 = 1 THEN rowFailed ← TRUE ENDIF

badBit ← block[failedRow][_________]

block[r][c] ← 1 _ block[r][c]

IF rowFailed ___ colFailed THEN flip(row, col) ENDIF

FOR col ← 0 TO 7 IF colFailed[col] THEN ________ ← col NEXT col

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A row ← 2

B col ← 3

C bit ← block[row][col]

D block[row][col] ← bit

Question 2

A FOR r ← 1 TO 4

B IF rowSum[r] MOD 2 = 1 THEN

C badCol ← r

D ENDIF

E NEXT r

Question 3

A OUTPUT "Row", badRow

B OUTPUT "Col", badCol

C OUTPUT "Bit", badRow, badRow

Question 4

A IF row > 0 OR col > 0 THEN

B bit ← block[row][col]

C block[row][col] ← 1 - bit

D ENDIF

Question 5

A FOR c ← 1 TO 5

B IF colSum[c] MOD 2 = 0 THEN

C col ← c

D ENDIF

E NEXT c

Answer Key

Finding the error in a parity block

Section A: Quick Questions

A — Find the row and the column that both fail their parity check. The error is where they cross.

A — At the one bit where row 3 meets column 5

A — Flip it: change a 0 to a 1, or a 1 to a 0

B — A parity block can locate a single-bit error, but a single parity bit can only show that an error happened.

B — The error is somewhere in row 2, but you do not know which column

Section B: Match the Pairs

Row 3 fails, column 5 fails → The changed bit is at the crossing point of row 3 and column 5

Flip bit at row 3, column 5: 1 -> 0 → Corrects a single-bit error once the changed bit has been found

The row and the column that both fail their parity check cross at the bit that has changed → Row 2 odd + column 4 odd -> error at row 2, column 4

A parity block can correct a single-bit error, which a single parity bit cannot → Error at row 2, column 4 is 0 -> flip it to 1

Only row 2 fails, so the error is the whole of row 2 → A failed row alone does not locate the bit. You also need the failed column, and the changed bit is where they cross.

Row 2 and column 4 fail, so the error is at row 4, column 2 → The row and column numbers are swapped. The error is at row 2, column 4, where the failed row and failed column cross.

Section C: Definitions

failed row and column — In a parity block, the row and the column that both fail their parity check cross at the bit that changed. Flip that bit to correct a single-bit error.

Section D: Fill in the Blanks

IF rowSum MOD 2 = 1 THEN
  rowFailed ← TRUE
ENDIF

badBit ← block[failedRow][failedCol]

block[r][c] ← 1 - block[r][c]

IF rowFailed AND colFailed THEN
  flip(row, col)
ENDIF

FOR col ← 0 TO 7
  IF colFailed[col] THEN errorCol ← col
NEXT col

Section E: Spot the Error

D — The bit at the crossing of the failed row and column has changed, so you must flip it with 1 - bit. Writing bit back leaves the error in place.

C — This loop checks rows, so a failed row number must be stored in badRow, not badCol. It should be badRow ← r.

C — The changed bit is at the crossing of the failed row and the failed column. The output must use badRow and badCol, not badRow twice.

A — A single-bit error makes both a row and a column fail. The test needs AND so the bit is only corrected when a failed row and a failed column cross.

B — With even parity, a column fails when it has an odd number of 1s. The test should be MOD 2 = 1, not 0, which would mark the columns that passed.