前回の練習問題について 情報記号 (x1, …, xk) に対し，検査記号 p = x1+…+xk+1として与えられる奇パリティ符号を考える．この符号が線形符号とならないことを証明せよ． 解答例： 線形符号とならない反例を示せばよい． x1=1, x2=x3=...=xk=0 ⇒ p = 0，対応する符号語は100...00 x2=1, x1=x3=...=xk=0 ⇒ p = 0，対応する符号語は010...00 ２つの符号語の和は110...0 ⇒ これは正しい符号語でない the quiz in the previous class - Show that odd parity check codes are not linear codes. A counterexample is shown in the slide. 100...00 and 010...00 are two codewords, but their sum 110...00 is not a codeword because it has even number of 1s. This means that the odd parity check code is not a linear code.

前回の練習問題について ６個の情報記号を，以下のように配置し，水平垂直パリティ検査符号を構成する．この符号の生成行列を求めよ a1 a2 p1 p2 q1 q2 q3 r (a1, ..., a6) → (a1, ..., a6, p1, p2, q1, q2, q3, r) the quiz in the previous class - Show the generator matrix of the given horizontal and vertical parity check code. We compute the matrix G which satisfies the equation in the middle of the slide. The parity check symbols are defined as the equations. (a1, ..., a6, p1, p2, q1, q2, q3, r) = (a1, ..., a6)G となる G を求める 検査記号の定義式は p1 = a1 + a2 + a3 p2 = a4 + a5 + a6 q1 = a1 + a4 q2 = a2 + a5 q3 = a3 + a6 r = a1 + a2 + a3 + a4 + a5 + a6

前回の練習問題について (a1, ..., a6, p1, p2, q1, q2, q3, r) = (a1, ..., a6)G となる G を求める 検査記号の定義式は p1 = a1 + a2 + a3 p2 = a4 + a5 + a6 q1 = a1 + a4 q2 = a2 + a5 q3 = a3 + a6 r = a1 + a2 + a3 + a4 + a5 + a6 a1 a2 a3 a4 a5 a6 p1 p2 q1 q2 q3 r the quiz in the previous class The first six symbols of the codeword are a_1, ..., a_6 themselves, and the left submatrix of G is a six-by-six identity matrix. The seventh column, which corresponds to the check symbol p_1, is defined so that it gives the sum of a_1, a_2 and a_3. The column vector must be (1 1 1 0 0 0)^T, which is the transpose of the coefficients of the equation for p_1. Note that the right submatrix of G is the transpose of the coefficient matrix of the definitions of the check symbols.

前回の内容について 線形符号は... 符号語集合がベクトル空間をなすような符号 検査記号が，情報記号の線形式で定義される符号 生成行列 基底符号語を行とする行列 符号化操作を効率的に行うための道具 review of the previous class linear codes: - linear codes are vector space, and - check symbols of a linear code is given as linear equations of information symbols generator matrix - a matrix whose row vectors are basis codewords of the code - contributes to realize efficient encoder

今回の内容 線形符号の復号操作（誤りの検出と訂正） 検査行列とシンドローム 1ビット誤りの訂正法 ハミング符号 １ビット誤り訂正可能な符号のクラス 完全符号（ある意味で，もっとも効率の良い符号）である today’s class - decoding operation of linear codes (correction and detection of errors) - check matrix and syndrome - correction of one-bit error - Hamming code - a class of one-bit error correcting codes - a perfect code

ある系列が符号語であるためには... 復号操作について考える前に...「符号語」である条件を整理する 水平垂直パリティ検査符号の場合： We are going to think about decoding operation, which is the most essential operation for error correcting codes. Before we proceed, we consider the condition for a vector to be a correct codeword. Assume that a codeword (x_1, ..., x_4, p_1, ..., r) is generated by multiplying a vector (x_1, ..., x_4) of information symbols to a generator matrix given in the slide. In this case, a vector (x_1, ..., x_4, p_1, ..., r) of length nine is a codeword if and only if the vector satisfies the five equations. 系列 (x1 x2 x3 x4 p1 p2 q1 q2 r) が「正しい」符号語 p1 = x1 + x2 p2 = x3 + x4 q1 = x1 + x3 q2 = x2 + x4 r = x1 + x2 + x3 + x4 必要十分条件

符号語であるための必要十分条件 各左辺を右辺に移項すると．．． ２進演算： x – y = x ＋ y x1 + x2 – p1 = 0 x3 + x4 – p2 = 0 x1 + x3 – q1 = 0 x2 + x4 – q2 = 0 x1 + x2 + x3 + x4 – r = 0 p1 = x1 + x2 p2 = x3 + x4 q1 = x1 + x3 q2 = x2 + x4 r = x1 + x2 + x3 + x4 Now we are considering binary equations. In this world, a “minus” equals to a “plus”, and the five equations are written as in the right-bottom representation. These equations gives a necessary and sufficient condition that a vector is a codeword. These equations are called parity check equations. ２進演算： x – y = x ＋ y (x1 x2 x3 x4 p1 p2 q1 q2 r) が「正しい」符号語 x1 + x2 + p1 = 0 x3 + x4 + p2 = 0 x1 + x3 + q1 = 0 x2 + x4 + q2 = 0 x1 + x2 + x3 + x4 + r = 0 パリティ検査方程式

検査行列 (x1 x2 x3 x4 p1 p2 q1 q2 r) が「正しい」符号語 x1 + x3 + q1 = 0 x2 + x4 + q2 = 0 x1 + x2 + x3 + x4 + r = 0 The parity check equations can be written in a vector-matrix representation. Replace variables and consider a vector (x_1, ..., x_9) of length nine. To test if this vector is a codeword, we multiply the transpose of this vector from the right to this matrix, and check if the result is a zero or not. If it becomes a zero vector, then all the parity check equations are satisfied and the vector is a codeword. If the multiplication is not zero, then it means that the vector violates one or more parity check equations, meaning that the vector is not a codeword. The matrix helps us checking if a vector is a codeword or not. For this reason, the matrix is called a (parity) check matrix. (x1 x2 x3 x4 x5 x6 x7 x8 x9) が 正しい符号語か？ 検査行列 系列を転置して，この行列 に右からかけ，0 になるかを 確かめれば良い． 0 ベクトル　⇒　符号語 0 ベクトル以外　⇒　符号語でない

検査行列の利用例 水平垂直パリティ検査符号 110101101 は符号語か？ yes 011011010 は符号語か？ no Here is a computation examples. 110101101 is a codeword because the multiplication of the check matrix and the vector is zero 011011010 is not a codeword because the multiplication is not zero. 011011010 は符号語か？ no

生成行列と検査行列 検査記号の定義式 生成行列 検査行列 k 行 n － k 行 単位行列 係数を転置した行列 係数行列 単位行列 p1 = a1,1x1 + a1,2x2 + ... + a1,kxk p2 = a2,1x1 + a2,2x2 + ... + a2,kxk : pm = am,1x1 + am,2x2 + ... + am,kxk a1,1x1 + a1,2x2 + ... + a1,kxk + p1 = 0 a2,1x1 + a2,2x2 + ... + a2,kxk + p2 = 0 : am,1x1 + am,2x2 + ... + am,kxk + pm = 0 We now learned a check matrix, but we already known another matrix, a generator matrix. The two matrices have strong relation to each other. Assume that parity check symbols are given by these equations. We transformed these equations so that they have zero on their right-hand sides, and a check matrix (right-bottom in the slide) is defined as the coefficient matrix of the equations. Remind that the generator matrix is also derived from the definitions of check symbols. The right submatrix of the generator matrix (left-bottom in the slide) is the transpose of the coefficients of the definition equations. Note that the right submatrix of the generator matrix and the left submatrix of the check matrix are in the transpose relation. The generator matrix and the check matrix have identity matrix in its left and right submatrix, respectively. If the codelength is n and the number of information symbols is k, then the generator matrix has k rows and n columns. On the other hand, the check matrix has n – k rows and n columns. 生成行列 検査行列 k 行 n － k 行 単位行列 係数を転置した行列 係数行列 単位行列

生成行列と検査行列 水平垂直パリティ検査符号： n = 9, k = 4, m = n － k = 5. p1 = x1 + x2 q1 q2 r p1 = x1 + x2 p2 = x3 + x4 q1 = x1 + x3 q2 = x2 + x4 r = x1 + x2 + x3 + x4 Here is an example of the generator and check matrices of a horizontal and vertical parity check code. You can see all the properties introduced in the previous slide. 生成行列 検査行列

シンドローム 検査行列： ある系列が，正しい符号語かどうか検査するのに有用 系列（の転置ベクトル）を，検査行列に右から掛ける 結果が 0 ベクトル　　　　　⇒　正しい符号語 結果が 0 ベクトルでない　⇒　符号語ではない The check matrix helps us testing if a vector is a codeword or not. We multiply the check matrix and a vector, and obtain a certain value. The value is called the syndrome of the vector. If the syndrome is zero, then the vector is a codeword, and we can expect that no error has occurred. If the syndrome is not zero, then the vector is not a codeword. Maybe one or more errors have occurred during the transmission, and one or more symbols have been altered unfortunately. The next step we consider: can we use the syndrome to “correct” errors? 系列の転置ベクトルを，検査行列に右から掛けて得られるベクトル 系列のシンドローム（syndrome）と呼ぶ シンドロームが 0 である系列　⇒　符号語 シンドロームが 0 でない系列　⇒　符号語でない シンドロームを用いて，誤りの訂正ができないか？

誤りを含む系列のシンドローム ２元対称通信路（BSC）に符号語 u を送信 誤りベクトル e が発生し，符号語に対して加法的に作用 受信系列は v = u + e 誤りが発生しなければ （e＝0)， 受信系列 v のシンドロームは0 誤りが発生したとすると （e≠0)， v のシンドロームは 0 以外 u e v = u + e 雑音源 符号語 受信系列 Assume that we are using a binary symmetric channel, and a sender has transmitted a codeword u. Also assume that an error vector e, which has the same vector length as u, has occurred and affected to u in an “additional” manner, meaning that it results in a vector v = u + e, where the addition is XOR. If there is no error (e = zero vector), then the received vector v equals to u, a codeword. In this case, as we have seen,, the syndrome of v = u equals to zero. If there are errors (i.e. e is not zero), then u is different from v, and it is strongly expected that the syndrome of v is not zero. Let H be a check matrix, then the syndrome of v is computed as in the slide. Note that the channel is additive, and that Hu^T equals to zero because u is a correct codeword. In summary, the syndrome of the received vector v is independent from the transmitted codeword, but depends on the error pattern e only. The same error pattern results in the same syndrome. If we see the syndrome, then we may be able to determine which error pattern causes the syndrome. 検査行列を H とすると，v のシンドロームは HvT = H(u + e)T = HuT + HeT = HeT. シンドロームは，送信符号語に依存せず，誤りにのみ依存する シンドロームを見ればどんな誤りが発生したかわかる

誤りパターンとシンドローム 000000000 を送信して 000100000 を受信したとすると， Assume that we are using this check matrix. If 000000000 is transmitted and 000100000 is received, then the syndrome of the recived vector is 01011. If 110000110 is transmitted and 110100110 is received, then the syndrome of the recived vector is 01011. Note that they have the same syndrome pattern. Also note that both of the received vectors have errors at the fourth bit of the vector. This means that, if the syndrome of a certain vector is 01011, then the forth symbol of the vector is expected to involve an error. 000000000 を送信して 000100000 を受信したとすると， H(0 0 0 1 0 0 0 0 0)T = (0 1 0 1 1)T. 110000110 を送信して 110100110 を受信したとすると， H(1 1 0 1 0 0 1 1 0)T = (0 1 0 1 1)T. 送信符号語に依存しない ⇒　シンドロームが (0 1 0 1 1) ならば，受信語の4ビット目が誤り

シンドロームを利用した誤り訂正 誤りパターンとシンドロームの対応がわかっていれば， 受信系列のシンドロームから誤りパターンを推測可能． 誤りパターンを受信系列から引く（足す）ことで， 送信符号語を特定可能 （誤りの影響を打消す / 誤り訂正）． Here is a procedure for the error correction. Assume that the relation between the error patterns and syndromes have been determined in advance. Given a received sequence v = u + e, we can compute the syndrome s of v. Actually, the syndrome s is the syndrome of the error pattern, and we can estimate the error pattern e. By subtracting the error pattern e from the received codeword v, we will be able to obtain the original codeword u. We have canceled the error and recovered the original information. 受信系列 シンドローム 誤りパターン 復号結果 v = u + e シンドローム計算 s = HvT s 誤り / シンドローム対応表 ..... e u

１ビット誤りパターンとシンドローム 符号長を n とし，検査行列 H の第 i 列目の列ベクトルを hi と書く： 誤りベクトルが e = (0 0 ... 0 1 0 ... 0) のときのシンドロームは i ビット目 You may think that it is too much to prepare the correspondence table of the syndrome and the error pattern. Fortunately, the preparation is not needed if consider one-bit errors only. Assume that the i-th column of the check matrix H is written as h_i. If the error pattern e has 1 at the i-th bit and 0 at the other bits, then the syndrome of e equals to h_i, the i-th column vector of H. That is, we the received vector involves only one error, at the i-th bit position, then its syndrome equals to the i-th column vector of the check matrix. If we can refer the check matrix, then we don’t need to record the relation between error patterns and syndromes. 受信系列の第 i ビット目だけに誤りが発生 ⇔　シンドロームは，検査行列の第 i 列ベクトルと等しい 　　（わざわざ対応表を作らなくてもOK）

シンドロームを使った誤り訂正 水平垂直パリティ検査符号 符号語 検査行列 000000000, 000101011, 001001101, 001100110, 010010011, 010111000, 011011110, 011110101, 100010101, 100111110, 101011000, 101110011, 110000110, 110101101, 111001011, 111100000. 検査行列 Here is an example of the error correction. Assume that we are using this check matrix. If the received vector is 101001000, then its syndrome is 10000^T. Now try to find 10000^T in the column vectors of H. We can see that the fifth column of H is 10000^T, and coincides with the syndrome. This means that the fifth symbol of the received vector involves an error. It is 0 in the received vector, but it must be 1 when it were transmitted. Actually, 101011000 is a correct codeword. Almost the same computation can be done for 101100110, for which we can find that an error occurs at the first bit position. 受信系列が 101001000 のとき， ⇒　シンドロームは H(1 0 1 0 0 1 0 0 0)T = (1 0 0 0 0)T ⇒　H の５列目と等しい ⇒　５ビット目が誤り，送信符号語は 101011000 受信系列が 101100110 のとき， ⇒　シンドロームは H(1 0 1 1 0 0 1 1 0)T = (1 0 1 0 1)T ⇒　H の１列目と等しい ⇒　１ビット目が誤り，送信符号語は 001100110

検査行列と符号の能力（１） 受信系列の第 i ビット目に誤りが発生 ⇔ シンドロームは，検査行列の第 i 列ベクトル 検査行列が同一の列ベクトルを複数含んでいると．．． ⇒　複数の１ビット誤りに対し，同一シンドロームが生成される ⇒　シンドロームからは，誤り位置の特定ができない The relation in the previous slides can be summarized as; a received vectors involves an error at the i-th bit position if and only if the syndrome of the received vector equals to the i-th column vector of the check matrix. Here is a simple question: what happens if some of column vectors of a check matrix are the same? In this case, an identical syndrome will be generated for different error patterns, and the received cannot determine correctly which error pattern has actually occurred. This is exactly the case for the even parity check code and the linear code which we consider in the previous class. In both cases, the check matrices have multiple columns with the same patterns. For this reason, these errors cannot correct one-bit errors. 誤り訂正能力のない符号 偶パリティ符号 p = x1 + x2 p1 = x1 + x2 p2 = x2 + x3 情報記号 (x1, x2, x3) に対し，

検査行列と符号の能力（２） 受信系列の第 i ビット目に誤りが発生 ⇔ シンドロームは，検査行列の第 i 列ベクトル もし検査行列の列ベクトルが全て異なっていれば．．． ⇒　異なる１ビット誤りパターンには異なるシンドロームが対応 ⇒　シンドロームから，誤り位置が一意に特定できる ⇒　符号語中の１ビット誤りを訂正可能 Consider the converse case. If the column vectors of a check matrix are all different, then different syndromes are generated for different error patterns. In this case, there is a unique correspondence between syndromes and one-bit error patterns, and we can determine the position of the error by looking at the syndrome. For example, if the check matrix is given as in the slide, then all the column vectors are different and the code can correct any one-bit error. 水平垂直パリティ検査符号 符号語中の１ビット誤りを訂正可能

誤り訂正符号の設計方針 符号語中の１ビット誤りを訂正可能な符号を構成したい 「列ベクトルが全て異なる検査行列」を持つ符号を作れば良い （簡単のため，検査行列の右部分行列は単位行列とする） Now consider to make use of this property to design a code which can correct one-bit errors. For this sake, we need to design the check matrix so that column vectors of the matrix are all different. For example, let H as defined in the slide. To make the discussion simple, we order column vectors so that the right-submatrix of the check matrix become an identity matrix. Note that the check matrix is a trivial representation of the coefficients of the parity check equations, and we can define the corresponding generator matrix from the parity check equations. Now we have constructed a one-bit error correcting code which has eight codewords given in the slide. たとえば とする. 符号語は 000000, 001011, 010101, 011110, 100110, 101101, 110011, 111000.

検査行列の大きさと符号の効率 検査行列が m 行 n 列 ⇒ 構成される符号は，符号長 n, 情報記号数 k = n － m, 水平垂直パリティ検査符号 n = 9 m = 5 符号長 9, 情報記号数 4. If the check matrix has m rows and n columns, then the defined code has the following parameters. the code length is n the number of information symbols is k = n – m the number of check symbols is m If the check matrix is “vertically long”, then the obtained code has many parity check symbols. This reduced the number of information symbols in a codeword, and the code become inefficient. This observation suggests a criteria to construct efficient codes. 検査行列が縦に長いと，符号語の中の検査記号数が多くなる ⇒　符号語の中の情報記号数が少なくなる ⇒　符号の効率は悪い

ハミング符号 符号語中の１ビット誤りを訂正可能な符号を構成したい できるだけ効率の良い符号を作りたい ⇒　できるだけ「横長」な検査行列を作れば良い． 1)　検査記号数 m を決定 2)　検査行列の列ベクトルとして，長さ m のベクトルを全て列挙 ゼロベクトルは列ベクトルに含めない （右部分行列が単位行列になるようにする） 他の列ベクトルの順番は，適当で良い ハミング符号 （Hamming Code）の構成法 We would like to construct an “efficient” “one-bit error correcting” code. - to make the code “one-bit error correcting”, we need to make the check matrix so that column vectors are all different - to make the code “efficient”, we need to make the check matrix so that it has horizontally long shape The Hamming code is the code constructed according to this policy. It is defined according to two steps. 1) choose a parameter m which becomes the number of check symbols in a codeword. 2) enumerate all nonzero vectors of length m, and define the check matrix by using the vectors as column vectors of the check matrix. - we don’t use a zero vector - we arrange the order of columns so that the right-submatrix becomes an identity matrix (this is not essential) - the order of other column vectors can be arbitrary The slide shows an example for choosing m = 3. In this case, there are 7 = 8 – 1 columns and the code length is 7. The number of check symbols is m = 3, and the number of information symbols is 7 – 3 = 4 bits. m = 3 の場合， 符号長（列数） 7, 検査記号数（行数） 3, 情報記号数 7－3 = 4．

ハミング符号のパラメータ ハミング符号の構成法 1) 検査記号数 m を決定する． 2) 検査行列の列ベクトル：長さ m のベクトル全て ゼロベクトルは列ベクトルに含めない 1) choose a parameter m which becomes the number of check symbols in a codeword. 2) enumerate all nonzero vectors of length m, and define the check matrix by using the vectors as column vectors of the check matrix. - we don’t use a zero vector The check matrix has m rows and 2^m – 1 columns. The code has the following parameters: the code length is n = 2^m – 1 the number of check symbols is m the number of information symbols is k = n – m = 2^m – 1 – m If the code length is n and the number of information symbols is k, then we say that the code is an (n, k) code. 検査行列は m 行 2m－1 列 m 2 3 4 5 6 7 n 15 31 63 127 k 1 11 26 57 120 符号長 n = 2m－1 検査記号数 m 情報記号数 k = n－m = 2m－1－m 符号長 n, 情報記号数 k の符号を （n, k) 符号と言う．

符号の比較 (7, 4) ハミング符号： 符号長 7, 情報記号数 4, 1 ビット誤り訂正可能 (9, 4) 水平垂直パリティ検査符号： 符号長 9, 情報記号数 4, 1 ビット誤り訂正可能 Now we have defined a (7, 4) Hamming code: This code has length seven, four information symbols and one-bit error correcting. We already know a (9, 4) horizontal and vertical parity check code: The code has length nine, four information symbols and one-bit error correcting. Which of the two codes is better? - The Hamming code is more efficient - The Hamming code is more reliable consider for example that the codes are used over a binary symmetric channel with the but error probability p. We can computer, for each code, the probability that the receiver succeeds in recovering a correct codeword. If p = 0.1, then we can see that the Hamming code has higher probability that the receiver receives correct information. Shorter codes are better. どちらの符号が「良い」か？ 効率ではハミング符号 情報伝達の信頼性でもハミング符号 ビット誤り率 p の BSC で，正しく情報を伝達できる確率 ハミング符号： 　　(1－p)7 + 7p(1－p)6 水平垂直パリティ検査符号：(1－p)9 + 9p(1－p)8 = 0.85 = 0.77 p=0.1 のとき 同じ情報記号数，同じ誤り訂正能力なら，符号長が短いほうが有利

符号パラメータの限界 (7, 4) ハミング符号： 符号長 7, 情報記号数 4, 1 ビット誤り訂正可能 同等以上の能力で，より効率的な符号はあるか？ 符号長 6, 情報記号数 4, 1 ビット誤り訂正可能な符号 We have seen that the (7, 4) Hamming code is better than the (9, 4) horizontal and vertical parity check code. The advantage of the Hamming code is derived mainly because it is shorter than the latter code. Then, a natural question arises. If there a code which is more efficient than the Hamming code? The code must has code length 6, 4 information symbols and one-bit error correcting. Unfortunately, such a code cannot exist. The proof is by contradiction: assume that such a code exists. - for each codeword, there are 1 + 6 = 7 vectors which are decoded to the codeword - different codewords have disjoint sets of vectors which are decoded to the codewords - the number of codewords is 2^4 =16, because we have four information symbols - there must exist 16 x 7 = 112 or more vectors with length 6 - the total number of vectors with length 6 is only 2^6 = 64, which cannot accomodate 112 vectors a contradiction. 存在しない！ ある符号語に復号される長さ 6 の系列は，1+6=7 通りある ある符号語に復号される系列は，他の符号語には復号されない 情報記号数は 4 なので，符号語は全部で 24=16 個 合計 16×7=112 通りの相異なる系列が存在するはず 長さ 6 の系列の総数は，全部で 26=64 個 ⇒　112通りの相異なる系列が存在するはずがなく，矛盾

ハミング符号の場合は... (7, 4) ハミング符号： 符号長 7, 情報記号数 4, 1 ビット誤り訂正可能 ある符号語に復号される長さ 7 の系列は，1+7=8 通りある ある符号語に復号される系列は，他の符号語には復号されない 情報記号数は 4 なので，符号語は全部で 24=16 個 合計 16×8=128 通りの相異なる系列が存在するはず 長さ 7 の系列の総数は，全部で 27=128 個 Consider the same discussion for the Hamming code: - for each codeword, there are 1 + 7 = 8 vectors which are decoded to the codeword - different codewords have disjoint sets of vectors which are decoded to the codewords - the number of codewords is 2^4 =16, because we have four information symbols - there must exist 16 x 8 = 128 or more vectors with length 7 - the total number of vectors with length 7 is only 2^7 = 128 We can see that all of the 128 codewords are neatly partitioned to 16 subsets, with each subset corresponds to a codeword. There is no interspace between the subsets. For this reason, the Hamming code is said to be a perfect code. 128 個の系列が，ちょうど 16 個の部分集合に分割される． ハミング符号は完全符号である．

少し高度な話題：多重誤り訂正符号 １ビット誤りが発生 ⇒ シンドロームは，誤り発生位置の列ベクトルと等しい ２ビット誤りが発生 ⇒ シンドロームは，誤り発生位置の列ベクトルの和と等しい In this lecture, we do not think of error correcting codes which can correct two or more errors, but there exist such codes. The syndrome of a one-bit error equals to the corresponding column vector of the check matrix. The syndrome of a two-bit errors equals to the sum of the corresponding column vector of the check matrix. If there are erros at the i-th and the j-th bit positions, then the syndrome is h_i + h_j. If the check matrix is designed so that the sums of different combinations of t or less column vectors are all different, then the code can correct up to t-bit errors. Design criteria for such codes are studied eagerly. i ビット目と j ビット目で誤りが発生 ⇒ シンドロームは hi + hj H の任意の t 個以下の列ベクトルの組合せに対し， それら列ベクトルの和が一意的である ⇒ t 重誤りを訂正可能 多重誤りを訂正できる線形符号の設計法も，多数存在

少し高度な話題：二重誤り訂正符号の例 この検査行列を持つ符号は，符号語中に発生した２ビットの 誤りを訂正することができる Here is an example of a check matrix of a two-bit error correcting code. Assume that we receive 11111000. The syndrome of this vector is 110111, which is the sum of the second and the sixth column vectors. This implies that the transmitted codewords weas 10111100. この検査行列を持つ符号は，符号語中に発生した２ビットの 誤りを訂正することができる 受信系列が 11111000 ⇒シンドロームは 110111T ⇒２ビット目，６ビット目が誤り ⇒送信符号語は 10111100

本日のまとめ 線形符号の復号操作（誤りの検出と訂正） 検査行列とシンドローム 1ビット誤りの訂正法 ハミング符号 １ビット誤り訂正可能な符号のクラス 完全符号（ある意味で，もっとも効率の良い符号）である summary - decoding operation of linear codes (correction and detection of errors) - check matrix and syndrome - correction of one-bit error - Hamming code - a class of one-bit error correcting codes - a perfect code

練習問題 ６個の情報記号を，以下のように配置し，水平垂直パリティ検査符号を構成する． この符号の検査行列を求めよ 110111001010 を復号せよ a1 a2 a3 a4 a5 a6 p1 p2 q1 q2 q3 r quiz: - Consider the illustrated code (this is the same one as the code given in the previous quiz). - determine the check matrix - decode the given sequence - Consider a (15, 11) Hamming code - give one of check matrices - give the generator matrix of constructed check matrix (a1, ..., a6) → (a1, ..., a6, p1, p2, q1, q2, q3, r) (15, 11)ハミング符号について， 検査行列（のひとつ）を作成せよ 生成行列を求めよ