Introduction to Binary Linear Block Codes Yunghsiang s.Han（韩永祥) School of Electrical Engineering Intelligentization Dongguan University of Technology(东莞理工学院) China E-mail:yunghsiangh@gmail.com
Introduction to Binary Linear Block Codes Yunghsiang S. Han （韩永祥） School of Electrical Engineering & Intelligentization Dongguan University of Technology (东莞理工学院) China E-mail: yunghsiangh@gmail.com
Y.S.Han Introduction to Binary Linear Block Codes Digital Communication System Modulator Encoder Digitized information Channel Errors Demodulator Decoder Received information School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 1 Digital Communication System Demodulator Channel Modulator Decoder Encoder ❄ ❄ ✛ ✲ ✛ ✲ ✛ Received information Digitized information Errors School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Introduction to Binary Linear Block Codes 2 Channel Model 1.The time-discrete memoryless channel (TDMC)is a channel specified by an arbitrary input space A,an arbitrary output space B,and for each element a in A,a conditional probability measure on every element b in B that is independent of all other inputs and outputs. 2.An example of TDMC is the Additive White Gaussian Noise channel (AWGN channel).Another commonly encountered channel is the binary symmetric channel(BSC). School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 2 Channel Model 1. The time-discrete memoryless channel (TDMC) is a channel specified by an arbitrary input space A, an arbitrary output space B, and for each element a in A , a conditional probability measure on every element b in B that is independent of all other inputs and outputs. 2. An example of TDMC is the Additive White Gaussian Noise channel (AWGN channel). Another commonly encountered channel is the binary symmetric channel (BSC). School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Introduction to Binary Linear Block Codes 3 AWGN Channel 1.Antipodal signaling is used in the transmission of binary signals over the channel. 2.A 0 is transmitted as +VE and a 1 is transmitted as-vE,where E is the signal energy per channel bit. 3.The input space is A={0,1}and the output space is B=R. 4.When a sequence of input elements(co,ci,...,cn-1)is transmitted, the sequence of output elements (ro,r1,...,rn-1)will be r5=(-1)VE+e, j=0,1,...,n-1,where ej is a noise sample of a Gaussian process with single-sided noise power per hertz No. 5.The variance of ej is No/2 and the signal-to-noise ratio (SNR)for the channel is y=E/No. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 3 AWGN Channel 1. Antipodal signaling is used in the transmission of binary signals over the channel. 2. A 0 is transmitted as + √ E and a 1 is transmitted as − √ E, where E is the signal energy per channel bit. 3. The input space is A = {0, 1} and the output space is B = R. 4. When a sequence of input elements (c0, c1, . . . , cn−1) is transmitted, the sequence of output elements (r0, r1, . . . , rn−1) will be rj = (−1)cj √ E + ej , j = 0, 1, . . . , n − 1, where ej is a noise sample of a Gaussian process with single-sided noise power per hertz N0. 5. The variance of ej is N0/2 and the signal-to-noise ratio (SNR) for the channel is γ = E/N0. School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Introduction to Binary Linear Block Codes 》 6. Pr(rilcj)= 1-g1-(-1)95E)2 -e √πN School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 4 6. P r(rj |cj ) = 1 √ πN0 e − (rj −(−1)cj √ E) 2 N0 . School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Introduction to Binary Linear Block Codes 5 Probability distribution function for ri The signal energy per channel bit E has been normalized to 1. 0.5 0.45 Pr(ril1)Pr(ril0) 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0 -4 -2 0 2 4 Ti School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 5 Probability distribution function for rj The signal energy per channel bit E has been normalized to 1. 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 -4 -2 0 2 4 rj P r(rj |1) P r(rj |0) 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 -4 -2 0 2 4 rj P r(rj |1) P r(rj |0) School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Introduction to Binary Linear Block Codes 6 Binary Symmetric Channel 1.BSC is characterized by a probability p of bit error such that the probability p of a transmitted bit 0 being received as a 1 is the same as that of a transmitted 1 being received as a 0. 2.BSC may be treated as a simplified version of other symmetric channels.In the case of AWGN channel,we may assign p as ● p= Pr(rill)dri = Pr(ril0)dri 1 (rj+vE)2 ViNGe No drj Q((2E/No) School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 6 Binary Symmetric Channel 1. BSC is characterized by a probability p of bit error such that the probability p of a transmitted bit 0 being received as a 1 is the same as that of a transmitted 1 being received as a 0. 2. BSC may be treated as a simplified version of other symmetric channels. In the case of AWGN channel, we may assign p as p = ∫ ∞ 0 P r(rj |1)drj = ∫ 0 −∞ P r(rj |0)drj = ∫ ∞ 0 1 √ πN0 e − (rj + √ E) 2 N0 drj = Q ( (2E/N0) 1 2 ) School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Introduction to Binary Linear Block Codes where 1-P 0 ·0 p 1. 。1 1-P Binary symmetric channel School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 7 where Q(x) = ∫ ∞ x 1 √ 2π e − y 2 2 dy ✟✟ ✟✟✟ ✟✯ ❍ ✲ q ❍❍❍❍❍❥ ✲ q q q 1 0 1 0 1 − p 1 − p p p Binary symmetric channel School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Introduction to Binary Linear Block Codes 8 Binary Linear Block Code (BLBC) 1.An (n,k)binary linear block code is a k-dimensional subspace of the n-dimensional vector space Vn={(co,c1,...,cn-1)Ivcj cjGF(2)};n is called the length of the code,k the dimension. 2.Example:a (6,3)code C={000000,100110,010101,001011, 110011,101101,011110,111000} School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 8 Binary Linear Block Code (BLBC) 1. An (n, k) binary linear block code is a k-dimensional subspace of the n-dimensional vector space V n = {(c0, c1, . . . , cn−1)|∀cj cj ∈ GF(2)}; n is called the length of the code, k the dimension. 2. Example: a (6, 3) code C = {000000, 100110, 010101, 001011, 110011, 101101, 011110, 111000} School of Electrical Engineering & Intelligentization, Dongguan University of Technology
Y.S.Han Introduction to Binary Linear Block Codes 9 Generator Matrix 1.An (n,k)BLBC can be specified by any set of k linear independent codewords co,c1,...,ck-1.If we arrange the k codewords into a k x n matrix G,G is called a generator matrix for C. 2.Letu=(uou1,·,uk-1),where u∈GF(2). c=(co,c1,.,cn-1)=uG. 3.The generator matrix G'of a systematic code has the form of [IkA],where Ik is the k x k identity matrix. 4.G can be obtained by permuting the columns of G and by doing some row operations on G.We say that the code generated by G'is an equivalent code of the generated by G. School of Electrical Engineering Intelligentization,Dongguan University of Technology
Y. S. Han Introduction to Binary Linear Block Codes 9 Generator Matrix 1. An (n, k) BLBC can be specified by any set of k linear independent codewords c0,c1,…,ck−1. If we arrange the k codewords into a k × n matrix G, G is called a generator matrix for C. 2. Let u = (u0, u1, . . . , uk−1), where uj ∈ GF(2). c = (c0, c1, . . . , cn−1) = uG. 3. The generator matrix G′ of a systematic code has the form of [IkA], where Ik is the k × k identity matrix. 4. G′ can be obtained by permuting the columns of G and by doing some row operations on G. We say that the code generated by G′ is an equivalent code of the generated by G. School of Electrical Engineering & Intelligentization, Dongguan University of Technology