PPT Slide

Complexity Issues (for codes in general)

Maximum Likelihood Decoding

Input: Generator matrix G, received word R

Output: closest (Hamming distance) codeword

Bounded Distance Decoding

Input: G, R, and “t”

Output: ALL codewords within distance t of R

Fractional Distance Decoding

Input: G, R, and t = ed (0 < e < 1)

Output: ALL codewords within distance t of R

Minimum Distance of a Code

Input: G, d

Output: Is the min dist of the code specified by G ? d?

Approximate Distance of a Code

Input: G

Output: approximate d’ = d ? a(n)d