- Perfect Code: Has no uncorrectable codewords with <=
*t*errors - Weight distribution: Set of count of codewords in a code each having the same weight
- E.g. 5 codewords have a weight of 1, etc.

- Weight enumerator: Polynomial function used to calculate the weight distribution of a code
- The coefficients for each degree are the count for that weight

- SEC-DED: Single error correcting, double error detecting

- Min distance of 3
- Corrects single bit errors
- Detects all <= 2 errors
- Is a perfect code (only one besides Golay code)
- Easily decoded using lookup table
- For any
*m*>= 3- Code Length = n = 2
^{m}-1 - Num. information bits = k = 2
^{m}-*m*-1 - Num. parity check bits = n - k =
*m* - Num. possible error corrections = t = 1
- Parity check matrix
**H**= [**I**_{m}**Q**]**Q**= collection of 2^{m}-*m*-1 columns with weight >= 2**I**_{m}=*m*x*m*identity matrix

- Generator matrix
**G**= [**Q**^{T}**I**_{2m-m-1}] - Standard array coset leaders =
**0**vector plus all 2^{m}-1 tuples with weight 1- This is why "Perfect Code" definition applies (corrects ALL single bit errors, and has NO other coset leaders besides the ones that correct <= t errors)

- Code Length = n = 2
- C++ Implementation here ((7,4) example from chapter 3)

- Made by deleting
*l*columns from**H**of a hamming code - Has following parameters:
- Code length = n = 2
^{m}-*l*- 1 - Num. information bits = k = 2
^{m}-*m*-*l*- 1 - Num. parity bits = n - k =
*m* - Num. possible error corrections = t = min distance > = 3

- Code length = n = 2
- If the columns are removed correctly, will have a min distance of 4
- In this case, can correct single bit errors and detect ALL double errors

- Decoding process
- If syndrome
**s**is**0**, no error occured - else
- If
**s**has odd number of 1s- result = (matching error pattern) +
**s**

- result = (matching error pattern) +
- else
- Uncorrectable error detected

- If

- If syndrome
- Weight enumerator: 1/(n+1) [(1+z)
^{n}) + n(1-z)(1-z^{2})^{(n-1)/2}]

- Multiple random error correction
- Simple construction
- Many choices for decoding (both hard and soft decision)
- Reed decoding algorithm
- Majority-Logic decoding algorithm
- Easily implemented

- Fo
*r*any*m*,*r*with 0 <=*r*<=*m*, denoted as RM(*r*,*m*)- Code length = n = 2
^{m} - Di
*m*ension = k(*r*,*m*) = 1 + bin(*m*,1)+bin(*m*,2)+...+bin(n,*r*)- bin(x,y) = bino
*m*ial coefficient

- bin(x,y) = bino
- Min distance = d
_{min}= 2^{m-r}

- Code length = n = 2
- Information bits can be reconstructed as different combinations of sums of the encoded bits
- e.g.
**u**_{0}=**v**_{0}+**v**_{1}+**v**_{2}+**v**_{3}=**v**_{4}+**v**_{5}+**v**_{6}+**v**_{7}= ... - These are called checksums

- e.g.
- Using the different possible combinations, majority vote on what the decoded bit should be
- The decoded bits are calculated recursively starting with longer checksums then getting shorter
- This is called "Majority Logic Decoding", with the number of recursive steps
giving the name "
*N*-step majority logic decoding" - Errors that happen in earlier steps of decoding affect later steps, called "error propogation"

- Two versions
- (23,12)
- (24,12)

- (24,12) has an additional parity bit
- Min distance of 8 for (24,12) or 7 for (23,12)
- Many uses, including U.S. space communication programs
- Only other perfect code besides Hamming
- Used as the primary error control system for NASA's
*Voyager*between 1979-1981, used to take pictures of Jupiter and Saturn - For the (24,12) code:
- Generator matrix
**G**= [**P****I**_{12}]**P**^{T}=**P**

**P**= parity matrix which can be found here (matrix*B*) - Parity check matrix
**H**= [**I**_{12}**P**] = [**I**_{12}**P**^{T}] - Decoding process:
- Compute syndrome
**s**= received ***H**^{T} - if weight(
**s**) <= 3- error vec
**e**= (**s**,**0**) (**0**is length 12) - Goto 8

- error vec
- if weight(
**s**+**p**_{i}) <= 2 for any row**p**_{i}in**P**- error vec
**e**= (**s**+**p**_{i},**u**^{i}) (**u**^{i}is 0 vec except a 1 in the*i*th position) - Goto 8

- error vec
- Compute
**s*****P** - if weight(
**s*****P**) == 2 or weight(**s*****P**) == 3- error vec
**e**= (**0**,**s*****P**) - goto 8

- error vec
- if weight(
**s*****P**+**p**_{i}) == 2 for any row**p**_{i}in**P**- error vec
**e**= (**u**^{i},**s*****P**+**p**_{i}) - goto 8

- error vec
- Decoding error if this step is reached and not skipped
- Calculate result = (received codeword) +
**e**

- Compute syndrome
- C++ Implementation here

- Generator matrix