Bài giảng Kỹ thuật truyền thông - Chương 5: Mã hóa kênh

, p(aj) là các xác suất của các từ mã đưa vào kênh
 (nguồn vào). p(b) là xác suất tổ hợp nhận được
 Luật giải mã cực tiểu hóa sai số chuyển về dạng sau do p(b) chung cả 2 vế:
 Chọn từ mã ai được truyền khi nhận được tổ hợp mã b, nếu :
 p(b/ai)(p(ai) >= p(b/aj)p(aj) với mọi ạj khác ai
 → Luật giải mã theo cực đâị hóa tương đồng giưa ai và b (Maximum Likelihood)
 Thường p(ai) = p(aj), luật giải mã chuyển thành:
 Chọn từ mã ai được truyền khi nhận được tổ hợp b, nếu:
 p(b/ai) >= p(b/aj) với mọi aj khác ai.
 → Luật giải mã theo cực đại hóa xác suất hậu nghiệm (Maximun Apriori Probability)
 8.3. Luật giải mã (Cont.)
• Ví dụ:
 • Một kênh BSC có ma trận kênh P, L=2, N=3. Các từ mã và xác suất xuất hiện
 của chúng cho bởi bảng trên. Tổ hợp nhận được là b=111
 • Tính:
     a2/a3/a4
 • Luật giải mã cực tiểu hóa sai số
 Chọn a4
5.4. Giải mã theo đa số
• Là phương pháp giải mã khi truyền lặp
 • Luật: ký hiệu nào xuất hiện nhiều nhất trong chuỗi ký hiệu nhận được từ
 chuỗi ký hiêụ truyền lặp cho 1 ký hiệu sẽ là ký hiệu được truyền.
• Mã lặp được thực hiện ở dạng mỗi ký hiệu mã đưa vào sẽ được lặp 
 lại chính nó một số lần.
 • Ký hiệu (n,m) ở đây n là số lần lặp cho một ký hiệu mã, m là số ký hiệu mã 
 của bản tin.
• Nếu một mã lặp nhị phân (n,1) được dùng, thì mỗi bít vào sẽ được 
 chuyển thành một chuỗi n bit trùng với nó. Thường n = 2t +1, t là số
 nguyên tùy chọn.
• Mã lặp có thể phát hiên (n-1)/2 lỗi.
 5.4. Giải mã theo đa số
 Thuật toán giải mã cho mã nhị phân (n,1):
 Vì n = 2t + 1 và giả thiết sai không vượt quá t vị trí, thì:
 Nếu tổng vị trí của tổ hợp nhận được có giá trị bằng 1, dH < t (số 0 
 nhiều hơn) thì chuỗi (từ mã) được truyền là toàn 0, ký hiệu được
 truyền là 0.
 Nếu tổng dH>t (số 1 nhiều hơn) thì từ mã được truyền là toàn 1, ký
 hiệu 1 được truyền.
 Ví dụ, mã nhị phân (5,1) và tổ hợp nhận được là b = 10110.
 Mã này có t = 2. Tổ hợp nhận được có dH =3. Vậy từ mã
 được truyền là 11111 và ký hiệu được truyền là 1. 
 5.5. Quãng cách Hamming
 Giả sử có hai từ mã dài N lký hiệu mã à a = a1..aN và b = 
 b1..bN
 Quãng cách Hamming giữa a và b, ký hiệu là d(a,b), được
 định nghĩa là số vị trí có ký hiệu mã khác nhau giữa hai từ mã.
 Quãng cách Hamming là độ đo được định nghĩa trên tất cả
 các cặp tổ hợp mã cùng độ dài.
 Quãng cách Hamming thỏa mãn các luật sau:
 d(a,b) >= 0
 d(a,b) = d(b,a)
 d(a,b) + d(b,c) >= d(a,c) (bất đẳng thức tam giác)
5.5. Quãng cách Hamming (cont.) 
• Ví dụ: cho N = 8
 • d(a,b) = 4, d(b,c) = 2, d(a,c) = 2
 • d(a,b) + d(b,c) = 4 + 2 ≥ d(a,c) = 2 
 5.5.1. Luật giải mã theo quãng cách 
 Hamming
 Số sai của kênh, ký hiệu là t, được định nghĩa là số vị trí sai lớn nhất
 kênh có thể gây ra cho một từ mã được truyền qua kênh.
 Giả sử b là tổ hợp mã dài N nhận được khi truyền từ mã ai dài N qua 
 kênh. Quãng cách Hamming giữa ai và b là d(ai,b) <= t. Quãng cách
 d(ai,b) = 0 khi ai = b hay kênh truyền không gây sai.
 Luật giải mã theo quãng cách Hamming là khi nhận được tổ hợp
 mã b và từ mã được truyền ai là (dựa theo luật giải mã cực đại hóa
 sự tương đồng): 
 - Nếu b = ai (d(ai,b) = 0) thì giải mã ai =b 
 - Nếu ai khác b thì với mọi ạj khác ai sẽ chọn aj là từ mã được
 truyền, nếu
 d(ai,b) <= d(aj,b), sai giải mã hay chấp nhận đường
 truyền gây ra trísốsaivị t = d(ai,b)
5.5.1. Luật giải mã
• Ví dụ:
 • Nếu nhận b = 000 →     a = 000
 • Nếu b ≠ 000 với sai quyết định t=1:
5.5.2. Quãng cách mã 
• Quãng cách mã, ký hiệu d(Kn): Quãng cách Hamming cực tiểu giữa 
 hai từ mã bất kz của bộ mã có từ mã dài N ký hiệu mã
 • d(Kn) = min (d(a,b)); Kn là bộ mã có các từ mã dài N ký hiệu mã
 • Ví dụ: Kn:
 d(Kn) = 2
 5.5.3. Phát hiện sai và sửa sai dùng 
 quãng cách Hamming 
• Phát hiện từ mã bị sai:
 • Mã khối, Kn, sẽ phát hiện được đến t sai khi và chỉ khi quãng cách mã thỏa mãn
 d(Kn) > t (5.1)
 • Công thức 5.1 là giới hạn về quãng cách mã của mã phát hiện được t sai.
 • Mã sẽ cho phép phát hiện đến t sai khi d(Kn) >= t+1.
 • Đồ hình minh họa phát hiện đến t sai khi d(Kn) = t+1: 
 • ai, aj là hai từ mã dài N. Mỗi vòng tròn biểu thị không gian của các tổ hợp sai của mỗi từ
 mã khi bị sai ≤ t vị trí
 5.5.3. Phát hiện sai và sửa sai dùng 
 quãng cách Hamming 
• Mã khối, Kn, sửa được đến t sai khi và chỉ khi quãng cách mã thỏa mãn:
 d(Kn) > 2t (5.2)
 • Công thức 5.2 là giới hạn về quãng cách mã để mã sửa được đến t sai.
 • Mã sẽ cho phép sửa đến t sai nêu d(Kn) >= 2t + 1
 • Đồ hình minh họa mã sửa được đến t sai khi d(Kn) = 2t+1: 
 • ai, aj là hai từ mã dài N, mỗi vòng tròn biểu diễn không gian các tổ hợp sai của mỗi từ mã 
 khi bị sai ≤ t vị trí 
5.5.3. 
 • Ví dụ:
 d(KN) = 2 →  1sa(t=1) vì 
 yêu cầu d(KN) > t, và không sửa được sai vì yêu cầu d(kn) >= 2t +1
5.5.3. 
 • Ví dụ
 • d(KN) = 3 Phát hiện được đến 2 sai, sửa được 1 sai
 5.6. Giới hạn về độ dài từ mã 
••
5.6. Giới hạn về độ dài từ mã
•
5.7. Xây dựng mã phát hiện sai/ sửa sai
•
 5.8. Mã Parity
•
 5.8. Mã Parity
•
 5.8. Mã Parity
• Ví dụ:
 • Tập bản tin (tổ hợp có thể): {00,01,10,11}. L = 2
 • 00, 11: tổ hợp chẵn → P=0
 • 10,01: tổ hợp lẻ → P =1
 • Bộ mã sẽ là: 
 000,110,101,011
 • Nếu nhận tổ hợp 010, thì s= 1, → sa
8.9. Hamming code
• Linear binary block code proposed by R. Hamming
• Can correct 1-error
• Have largest length:
 • According to (8.4) N-L ≥ 
 • r = 2, t = 1 N-L ≥ (1 +N) ≥ 1 + N N - 1
 • Nmax = - 1
• Hamming code uses linear space to represent code
 • Code that uses linear space called linear code
8.9. Hamming code (cont.)
• Linear space
 • A vector space over a field F is a set V together with two operations that 
 satisfy the eight axioms listed below.
 • The first operation, called vector addition or simply addition +
 • u, v ϵ V w = u +v ϵ V 
 • The second operation, called scalar multiplication .
 • u ϵ F , v ϵ V w = u . v ϵ V
8.9. Hamming code (cont.)
• Linear space
 • Axioms:
 • Associativity of addition u + (v + w) = (u + v) + w
 • Commutativity of addition u + v = v + u
 • Identity element of addition There exists an element 0 ∈ V, called the zero vector, such 
 that v + 0 = v for all v ∈ V.
 • Inverse elements of addition For every v ∈ V, there exists an element −v ∈ V, called the 
 additive inverse of v, such that v + (−v) = 0.
 • Compatibility of scalar multiplication with field multiplication a(bv) = (ab)v 
 • Identity element of scalar multiplication 1v = v, where 1 denotes the multiplicative identity 
 in F.
 • Distributivity of scalar multiplication with respect to vector addition a(u + v) = au + av
 • Distributivity of scalar multiplication with respect to field addition (a + b)v = av + bv
 8.9. Hamming code (cont.)
• Linear space
 • If the element of V is N-dimension vector then V is called N-dimension vector space 
 • a ∈ V then a = a1,a2,,aN
 • ai has discrete values from 0 to r-1 discrete space with base r
 • Generic matrix
 • Set of N independent elements of V called set of base elements
 • Base elements are denoted by g1,g2,..gN 
 • Set of base elements can generate all elements of V
 • Arrange each N-dimension element in one row N x N matrix whose rows are independent. 
 • This matrix is called generic matrix (G)
 • a ∈ V if and only if a = C .G a = a = a1a2..aN
 • C is coefficient vector 
 • In discrete space with base r: value of ci is 0/1//r-1
 • C has values
 • a = C .G can generate all N-dimension elements of space
 • If G is unit matrix
 • G is in canonical form
 • a is called systematic code
 • k first symbols are carrying information symbols, remaining symbols are checked symbols
8.9. Hamming code (cont.)
• Linear space
 • L-dimension subspace (L<N) is a subspace of N-dimension space.
 • Each element of L are N-dimension elements
 • Has maximum L independent elements
 • Can be considered as set of base elements of subspace
 • Generic matrix has L rows, N columns (
 • One element a ∈ if and only if a = C . while C=c1c2cL
 • Number elements of subspace is 
 • is in canonical form when its first (L x L) submatrix if unit matrix 
 • N-L dimension subspace: 
 • its elements are orthogonal with N-dimension subspace
 • Called orthogonal space
 • Generic matrix has (N-L) row, N columns ()
 • . = 0
 • a ∈ if and only if a. = 0
 • is called “check parity matrix”
 • is in canonical form when its first ((N-L) x (N-L)) submatrix if unit matrix
 8.9. Hamming code (cont.)
• Linear code: 
 • One codeword of linear code is mapped to one element of L-dimension 
 subspace
 • Other elements of N-dimension space which don’t belong to L-dimension 
 subspace is “don’t care combination”
 • With linear code: if a is codeword then a is generated by a = C.G
 or a satisfies a. =0
 • To simplify is denoted by G, is denoted by H
 • To decode: when receive b, calculate syndrome S = b.
 • S = 0: no error
 • S > 0 : error
 • Since b = a + e where e = { ,, } is “error combination”, S = e. 
 e can be calculated using S
 8.9. Hamming code (cont.)
• Hamming code:
 • To build Hamming code or to decode a codeword of Hamming code, Hamming 
 uses only “check parity matrix” H
 • Hamming proposes: each column of check parity matrix is a (N-L) binary 
 number 
 • The value of binary number = order number of column 
 • Hamming code is binary code that can correct 1-error 
 • Length of Hamming code N = - 1
 • To build: Solve a=0 to determine codeword a 
 • If a= is codeword needed to be built then a=0
 • a=0 is matrix equation which generates system of (N-L) first-order equations
 • ai = 0 when hi is the i-th row of matrix H
 • Systems of equations can only determine (N-L) ai, other L symbol ai of a will be given parameters
 • Given parameters are L-symbol message 
 • ai are given parameters
 • Its position corresponds with column order of matrix H
 • The column has only value 1
8.9. Hamming code (cont.)
• Hamming code:
 • To decode:
 • Let b is received combination, need to calculate syndrome S = 
 • If S = 0 no error
 • If S ≠ 0 S = e. = where is ith column of matrix H with the wrong position is i
 • binary number that has value = i Syndrome indicates wrong position
8.9. Hamming code (cont.)
• Example
 • L = 4, t = 1, r =2
 • Let message m = {m1,m2,m3,m4}
 • N is calculated by N = 2^ (L – 1) - 1 N = 7 
 • Check matrix (check parity matrix):
 • H =
 • Position 1,2,4 of matrix H has only one position that has value = 1
 a = (x,y,m1,z,m2,m3,m4)
 then a = {z+m2+m3+m4, y+m1+m3+m4,x+m1+m2+m4} = {0,0,0}
8.9. Hamming code (cont.)
• x = m1+ m2+ m4
• y = m1+m3+m4
• z= m1+m2+m3
 a = {m1+m2+m4, m1+m3+m4, m1,m1+m2+m3,m2,m3,m4} 
• Input: L-symbol message
• Output: N-symbol codeword 
8.10.Cyclic code
• 8.8.1
• 8.8.2
8.8.1 Galois field
• Field: field is a set of elements and operations of addition and 
 multiplication. The operations must follows rules below
 • Closed: Closure impliles that the sum and product of any two elements in 
 the field are also elements of the field
 • Commutative (ab = ba and a+b = b+a)
 • Associative (a(bc) = (ab)c, and a + (b + c) = (a + b) + c)
 • Distributive law relates multiplication and addition: a(b + c) = ab + ac.
 • Has additive and multiplicative identities (0 and 1) such that a + 0 = a and 1a 
 = a for any element in the field.
 • Elements of a field must have additive and multiplicative inverses. The 
 additive inverse of a is an element b such that a+b = 0 and the multiplicative 
 inverse of a is an element c such that ac = 1.
 • E.g: 
 • set of real numbers and addition, multiplication creates field. 
8.8.1 Galois field
• Finite field: 
 • Denoted by Zp that contains
 • The set of integers {0, 1, .., p−1} 
 • Modulo p arithmetic. 
 • p is a prime number
• Galois field: GF () contains
 • p is prime number
 • n is arbitrary positive integer
 • Each element is denoted by polynomial a1+ a2+.+ aN where the coefficients ai take on 
 values in the set {0, 1, ..., p − 1}. 
 • To add two polynomials, for each power of x present in the summands, just add the 
 corresponding coefficients modulo p
 • a(x)= a1+ a2+.+ aN
 • c(x) = a(x)+b(x) = (a1b1) + (a2b2)x + + (aN bN)
 • ai = ai+bi if ai+bi <p
 = ai +bi –p if ai+bi >=p
 • Multiplication of two polynomials is done by multilication in modulo where is modulo 
 polynomial a(x) x b(x) modulo ( ) = reminder of ((a(x) x b(x))/ )
8.8.2 Definition
 • Cyclic code uses Galois Field GF()
 • Codeword a is considered as polynomials 
 • E.g. a = {,,,} is considered as a(x)= + +.+ 
 • Multiplication is calculated in modulo 1
 • Multiple with x is equivalence to right shift its coefficients
 xa(x) = a0 + a1x^1 + a2x^2 +.+a(N-1) +aN(x^n -1)
 xa(x) modulo(x^n -1) = aN + a0x^1+a1x^2 +.+ a(N-1)
 • Cyclic code is a linear code with the property that any cyclic shift of a code word is 
 also a code word
 • A cyclic code has a unique non-zero polynomial of minimal degree
 • This polynomial is called generator polynomial with degree r:
 g(x) = g0 + g1x^1 ++ grx^r
 • g(x) is the generator polynomial of a cyclic code if and only if it is a factor of (X^N-1)
 • The remainder of division between arbitrary codeword and g(x) =0 
 • If c(x) is codeword then c(x) = m(x) g(x) 
8.8.2. Definition(Cont.)
• Generator matrix:
 • G is a cyclic matrix (each row is obtained by shifting the previous row one 
 column to the right).
8.8.2. Definition(Cont.)
• Since g(x) is the factor of -1), that 
 -1) = g(x) h(x)
 Where h(x) is called check parity matrix
 • If c(x) is codeword then c(x) h(x) = m(x) g(x) h(x) modulo -1) = 0
 • h(x) = x ++ 
• Check parity matrix H: is a cyclic matrix (each row is obtained by 
 shifting the previous row one column to the right).
 • First row is h(x)
8.8.3.Encoding and decoding
• Encoding process is multiple generator polynomial g(x) with carrying 
 information (message) polynomial m(x)
 • c(x) = m(x) g(x)
• Decoding process:
 • Syndrome S is remainder of division between received polynomial r(x) and 
 g(x)
 • S = r(x) mod g(x) modulo -1)
 • If S = 0 codeword
 • If S 0 S = e(x) mod g(x) modulo -1) 
 • Can find error polynomial e(x) from S 
8.8.3.Encoding and decoding (Cont.)
• If generator matrix G is transformed into canonical form, codeword is 
 in systematic form
 • c(x) = m(x) + d(x) 
 Where d(x) is a polynomial has degree of n-k-1
• Since c(x) mod g(x) modulo-1) = 0,
 then d(x) = m(x) mod g(x) modulo-1)
8.8.4. Cyclic Redundancy Check Codes
• Is cyclic systematic code
• Used for send or store the information
• Codeword c(x) = m(x) – crc
 • crc = m(x) mod g(x) modulo – 1)
• Decoding
 • Let r(x) = m’(x) – crc’ where m’(x) = m(x) + (x); crc’=crc+ (x)
 • (x) first L symbol of e(x)
 • (x) remaining N-L symbols of e(x)
 • S= m’(x) mod g(x) modulo – 1) – crc’
 • S= 0 no error
 • S 0 S = (x) mod g(x) modulo – 1) - (x)
 • Calculate (x), (x) from S