• 2-dimensional parity check
• parity check over a block of consecutive data units
• each data unit contains VRC parity bit
• append data unit containing parity bit for corresponding bit position across all data units in block
• cannot detect even numbers of errors in corresponding positions of even numbers of data units. (e.g. units 2 and 4 both have errors in bit positions 5 and 7).

Concerning the terms vertical and longitudinal:

• CRC bits are appended.
• CRC value is such that combination of data and CRC bits form value divisible by "well-known" divisor (the generator polynomial).
• if receiver gets non-zero remainder, error occurred.
• uses modulo-2 arithmetic
• CRC generator (sender):
• start with original data M, r-degree generator polynomial G.
• append r 0’s to data, result is M'.
• divide M' by G, yielding quotient Q and remainder R.
• add R to M', yielding T.
• transmit T.
• CRC check (receiver):
• start with received data T+E, generator polynomial G.
• divide T+E by G, yielding quotient Q and remainder R
• if R is 0 then E is 0. truncate the last r bits of T and pass on.
• if R is not 0, then E is not 0. An error has occurred.
• polynomial representation
• divisor bit string usually expressed as polynomial on x
• exponent represents bit position and coefficient is bit value (0 or 1).
• example: string 100101 represented as x⁵+x²+1.
• there are standard generator polynomials
• CRC-16 : x¹⁶+x¹⁵+x²+1 (17 bit generator, yields 16 bit CRC)
• CRC-ITU : x¹⁶+x¹²+x⁵+1
• CRC-32 : (33 bit poly with many terms)

• probabily of undetected error is quite small.

• Hamming distance
• given encoding, minimum # bits that must be flipped to change one valid code into another valid code.
• Example: Hamming distance for ASCII is 1.
• Example: encoding 1001, 0011, 1100, 0110, 1010, 0101, 0000, 1111 has distance 2 and can encode 8 values.
• n-bit errors can be detected if Hamming distance is n+1
• n-bit errors can be corrected if Hamming distance is 2n+1
  
• Hamming code (1950)
• allows receiver to determine which bit was flipped.
• redundancy bits placed in specific bit positions; each represents VRC over specific bit positions
• assume bit positions numbered starting with 1. Bit positions of redundancy bits are powers of 2 (1,2,4,8,etc). Redundancy bit in position i represents VRC over bit positions whose binary representation has 1 in its bit position i!
• Example: redundancy bit in position 1 is VRC for all odd-numbered bit positions: 1,3,5,7, etc (binary representation has 1 in position 1). Redundancy bit in position 3 is VRC for bit positions 4,5,6,7 (binary representation has 1 in position 3). Note the overlaps.
• number of redundant bits r required for unit of m data bits determined by smallest r such that 2^r >= m + r + 1

Last reviewed: 18 February 1998