北京邮电大学计算机学院 离散数学 数学结构 解码 chap11-2.ppt

* * College of Computer Science Technology, BUPT New procedure Step 1: Determine all left cosets of N = eH(Bm ) in Bn. Step 2: For each coset, find a coset leader, and compute the syndrome of each leader Step 3: If xt is received, compute the syndrome of xt and find the coset leader ? having the same syndrome. Then xt ? ? = x is a code word eH(b), and d(xt) = b. * * College of Computer Science Technology, BUPT Example 5 Consider the parity check matrix and the (3, 6) group code eH: B3 ? B6. * * College of Computer Science Technology, BUPT Example 5 N = {000000, 001011, 010101, 011110, 100110, 101101, 110011, 111000} Syndrome of Coset Leader | Coset leader --------------------------+------------------- 000 | 000000 001 | 000001 010 | 000010 011 | 001000 100 | 000100 101 | 010000 110 | 100000 111 | 001100 --------------------------+------------------- * * College of Computer Science Technology, BUPT Example 5 If xt = 001110, then fH(xt) = xt * H = 101, same as ?=010000. x = xt ? ? = 001110 ? 01000 = 011110 = e(011), so decode 001110 as 011. Syndrome of Coset Leader | Coset leader --------------------------+------------------- 000 | 000000 001 | 000001 010 | 000010 011 | 001000 100 | 000100 101 | 010000 110 | 100000 111 | 001100 --------------------------+------------------- * * College of Computer Science Technology, BUPT ((( ))) Please feel free to ask questions! * * College of Computer Science Technology, BUPT Key ideas for review Message, word (m, n) encoding function, one-to-one Code word, parity check code Detect, correct, k or fewer errors Hamming distance Properties of distance Group code and parity check matrix Minimum distance of a group code Maximum likelihood technique Maximum likelihood decoding function Syndrome and decoding procedure for group code Good luck to you all! College of Computer Science Technology, BUPT Discrete Mathematical Structures Yang Juan yangjuan@bupt.edu.c