introduction-basic-concepts.md (2537B)
1 +++ 2 title = "Introduction, basic concepts" 3 template = "page-math.html" 4 +++ 5 6 # Introduction, basic concepts 7 Some definitions: 8 - digit: 0, 1 9 - word: sequence of digits 10 - length: digits in word (|word|) 11 - binary code: set C of words 12 13 assumptions about transmission channel: 14 - length of sent == length of received 15 - easy to find beginning of first word 16 - noise scattered randomly (not in bursts) 17 18 properties of binary channel: 19 - symmetric if 0 and 1 transmitted with same accuracy 20 - reliability: probability that digit sent == digit received 21 - we assume ½ ≤ p < 1 22 23 information rate of code (length n) = $\frac{1}{n} \log_{2} |C|$ 24 25 ## Most likely codeword 26 Let $\phi_{p} (v,w)$ be probability that if word v sent over BSC with reliability p, word w is received. 27 28 $\phi_{p} (v, w) = p^{n-d} (1-p)^d$ if v and w disagree in d positions. 29 30 if v₁ and w disagree in d₁, and v₂ and w in d₂, then $\phi_{p} (v_{1}, w) \leq \phi_{p} (v_{2}, w)$ iff d₁ ≥ d₂. 31 - English: the most likely word disagrees in least digits 32 33 ## Weight and distance 34 35 K = {0, 1}, $K^{n}$ = set of all binary words of length n 36 37 (Hamming) weight: number of ones 38 39 (Hamming) distance: number of differing digits between words 40 41 ## Max likelihood decoding (MLD) 42 Complete: 43 - if one word min distance, decode to that 44 - else, arbitrarily select one of closest 45 46 Incomplete: 47 - if one word min distance, decode to that 48 - else, ask for retransmission 49 - look for smallest weight in error patterns with C, e.g. 0+w and 1+w 50 - retransmit if same weight 51 52 Reliability: probability that if v sent over BSC of prob b, then IMLD concludes that v was sent 53 54 $\theta_{p} (c, v) = \sum_{w \in L(v)} \phi_{p} (v, w)$ where $L(v) = \lbrace words \in K^{n} \enspace \| \enspace \text{IMLD correctly concludes v sent} \rbrace$ 55 56 ## Error-detecting codes 57 error pattern is u = v + w if v ∈ C sent and w ∈ Kⁿ received. 58 59 error detected if u is not a codeword. 60 error patterns that can't be detected are sums of codewords 61 62 distance of code: smallest d(v, w) ∀v,w. 63 64 Code of dist d at least detects patterns of weight d-1, there's at least one pattern of weight d not detected. 65 66 t-error-detecting code if detects pattern weight max t, and does not detect at least one pattern of weight t+1. 67 so code with dist d is "d-1 error-detecting code" 68 69 ## Error-correcting codes 70 Code C corrects error pattern u if ∀v ∈ C, v+u closer to v than any other word 71 72 Code of dist d corrects all error patterns $weight \leq \frac{d-1}{2}$, at least one pat weight $1+\frac{d-1}{2}$ not corrected.