›
›

Kỹ thuật truyền dẫn viba số

ppt 35 trang phuongnguyen 80
Download
Bạn đang xem 20 trang mẫu của tài liệu "Kỹ thuật truyền dẫn viba số", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptky_thuat_truyen_dan_viba_so.ppt

Nội dung text: Kỹ thuật truyền dẫn viba số

  1. KỸ THUẬT TRUYỀN DẪN VIBA SỐ
  2. Xử lý baseband a. Linear Block Coding  Trong loại mã này luồng thông tin được chia thành các khối có độ dài bằng nhau được gọi là các khối dữ liệu. Các bit nhận được ở đầu ra của bộ mã hoá được gọi là từ mã. Các bit được thêm vào các khối theo một thuật toán nhất định phụ thuộc vào loại mã được sử dụng, các bit này thường được gọi là các bit kiểm tra. Mã khối được xác định bằng ba thông số: độ dài khối dữ liệu k, độ dài từ mã n và khoảng cách Hamming cực tiểu dm. Tỷ số r = k/n được gọi là tỷ lệ mã. Các bit kiểm tra có độ dài n-k. Bộ mã hoá được ký hiệu (n,k).  Sơ đồ khối tổng quát của một bộ mã hoá khối tuyến tính như sau
  3. Xử lý baseband K bit dữ liệu vào Từ mã n bit ra Mã hóa 1001001001001110 1001110001011101001101110100 Trong mã khối tuyến tính các bit ngõ ra được xem như là tổ hợp tuyến tính của các bit ngõ vào. Gọi ma trận[M ]= [ m12 m mk ] tượng trưng cho khối dữ liệu k bit dữ liệu ngõ vào Gọi ma trận [T ]= [ t12 t tn ] tượng trưng cho từ mã n bit ngõ ra
  4. Xử lý baseband • Theo định nghĩa các bit ngõ ra có thể được diễn tả bằng hệ phương trình sau: t1= g 11 m 1 + g 21 m 2 + + gkk 1 m t2= g 12 m 1 + g 22 m 2 + + gkk 2 m tn= g1 n m 1 + g 2 n m 2 + + g kn m k [][][]TMG=• • Có thể viết lại hệ phươngg11 g 12 trình g 1 ntrên dưới dạng ma trận g g g []G = 21 22 2n gk12 g k g kn
  5. Xử lý baseband • Để mã có tính chất hệ thống thì khối dữ liệu ngõ vào phải tồn tại trong từ mã ngõ ra vì thế ma trận [T] có dạng như sau: T =  m1 m 2 mk c 1 c 2 c n− k  • Trong đó các bit c1 cn-k là các bit kiểm tra được thêmt= mvào = g. Vì m +thế g mk + phương + g m trình đầu trong hệ 1phương 1 11trình 1được 21 2viết lạikk 1 t2= m 2 = g 12 m 1 + g 22 m 2 + + gkk 2 m tk= m k = g1 k m 1 + g 2 k m 2 + + g kk m k
  6. Xử lý baseband • Hệ phương trình trên chỉ thỏa với 1 ij= gij = 0 ij • Do đó ma trận sinh được xác định: 1 0 0 gg1kn+ 1 1 0 1 0 gg G = 2kn+ 1 2 0 0 0 1 ggkk+1 kn I P
  7. Xử lý baseband • Ví dụ: Mã (7,4) có ma trận sinh
  8. Cyclic block codes • Mã vòng là một biến thể của mã khối tuyến tính. • Việc mã hóa và tính các syndrome có thể thực hiện dễ dàng bằng các thanh ghi dịch có hồi tiếp feedback shift-registers. – Có thể sử dụng các mã có độ dài hơn, phức tạp hơn. • Điển hình là mã BCH (Bose – Chaudhuri – Hocquenghem) và Reed-Solomon.
  9. Cyclic block codes • Mã khối tuyến tính (n,k) được gọi là mã vòng nếu tất cả quá trình dịch vòng của một từ mã cũng tạo ra từ mã “i” cyclic shifts of U U = (u0 ,u1,u2 , ,un−1) (i) U = (un−i ,un−i+1, ,un−1,u0 ,u1,u2 , ,un−i−1) Example: U = (1101) U(1) = (1110) U(2) = (0111) U(3) = (1011) U(4) = (1101) = U
  10. Cyclic block codes • Có thể biểu diễn từ mã của mã vòng như là một đa thức đại số 2 n−1 U(X ) = u0 + u1 X + u2 X + + un−1 X degree (n-1) Mối liên hệ giữa từ mã và quá trình dịch vòng: 2 n−1 n XU(X ) = u0 X + u1 X + ,un−2 X + un−1 X = u + u X + u X 2 + + u X n−1 + u X n + u n−1 01 n−2 n−1n−1 (1) n U ( X ) un−1 ( X +1) (1) n = U (X ) + un−1(X +1) Hence: U(1) (X ) = XU(X ) modulo (X n +1) By extension U(i) (X ) = X iU(X ) modulo (X n +1)
  11. Cyclic block codes  Một số tính chất cơ bản của mã vòng:  Giả sử C là mã vòng tuyến tính (n,k) 1. Với tất cả các đa thức mã trong C thì có duy nhất đa thức nguyên tố g(X ) với bậc nhỏ nhất r n. g(X ) được gọi là đa thức sinh generator polynomials. r g(X ) = g0 + g1 X + + gr X 2. Mỗi đa thức mã U(X ) trong C, có thể được biểu diễn duy nhất U(X ) = m(X )g(X ) 3. Đa thức sinh là hệ số của X n +1
  12. Cyclic block codes 4. Tính trực giao của đa thức G và H được diễn tả g(X )h(X ) = X n +1 . Nghĩa là h(X ) là hệ số của X n +1 5. Hàng thứ i,i =1, , k của ma trận sinh được hình thành từ các hệ số của đa thức sinh được dịch đi "i −1" vòng g g  g 0 g(X ) 0 1 r g g  g Xg(X ) 0 1 r G = =      g0 g1  gr X k−1g(X ) 0 g0 g1  gr
  13. Cyclic block codes • Systematic encoding algorithm for an (n,k) Cyclic code: 1. Multiply the message polynomial m ( X ) by X n−k 2. Divide the result of Step 1 by the generator polynomial g ( X ) . Let p ( X ) be the reminder. 3. Add to X n − k m ( X ) to form the U(X ) codeword Remember CRC used to detect errors in packets? “Cyclic” Redundancy Check: same idea!
  14. Cyclic block codes • For the systematic (7,4) Cyclic code with generator Example: 3 polynomial g(X ) =1+ X + X 1. Find the codeword for the message m = (1011) n = 7, k = 4, n − k = 3 m = (1011) m(X ) =1+ X 2 + X 3 X n−km(X ) = X 3m(X ) = X 3 (1+ X 2 + X 3 ) = X 3 + X 5 + X 6 Divide X n−km(X ) by g(X): X 3 + X 5 + X 6 = (1+ X + X 2 + X 3 )(1+ X + X 3 ) + 1   quotientq (X) generator g(X) remainder p( X ) Form the codeword polynomial : U(X ) = p(X ) + X 3m(X ) =1+ X 3 + X 5 + X 6 U = (1 0 0 1 0 1 1) parity bits message bits
  15. Example: Encoding of systematic cyclic codes
  16. Cyclic Codes
  17. Decoding cyclic codes Table 16.6 s( x )= mod r ( x )/ g ( x ) gx()
  18. Cyclic block codes 2. Find the generator and parity check matrices, G and H, respectively. 2 3 g(X ) =1+1 X + 0 X +1 X (g0 , g1, g2 , g3 ) = (1101) 1 1 0 1 0 0 0 Not in systematic form. 0 1 1 0 1 0 0 G = We do the following: 0 0 1 1 0 1 0 row(1) + row(3) → row(3) 0 0 0 1 1 0 1 row(1) + row(2) + row(4) → row(4) 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 0 G = H = 0 1 0 1 1 1 0 1 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 1 T I3 3 P P I4 4
  19. Cyclic block codes  Syndrome decoding for Cyclic codes:  Received codeword in polynomial form is given by Received r(X ) = U(X ) + e(X ) Error codeword pattern  The syndrome is the reminder obtained by dividing the received polynomial by the generator polynomial. r(X ) = q(X )g(X ) + S(X ) Syndrome  With syndrome and Standard array, error is estimated.  In Cyclic codes, the size of standard array is considerably reduced.
  20. x0 x1 xn-1 0 received code 1 syndrome G(p )= p3 + p + 1 To start with, the switch is at “0” position Then shift register is stepped until all the received code bits have entered the register This results is a 3-bit syndrome (n - k = 3 ): SRG(p )= mod ( p )/ ( p ) that is then left to the register Then the switch is turned to the position “1” that drives the syndrome out of the register Note the tap order for Galois-form shift register 20
  21. PB 8PSK QPSK Eb / N0 [dB] 2005-02-09 Lecture 8 21
  22. Well-known Cyclic Codes • (n,1) Repetition codes. High coding gain, but low rate • (n,k) Hamming codes. Minimum distance always 3. Thus can detect 2 errors and correct one error. n=2m-1, k = n - m, m 3 • Maximum-length codes. For every integer m there 3 exists a maximum k k-1 length code (n,k) with n = 2 - 1,dmin = 2 . Hamming codes are dual of maximal codes. • BCH-codes. For every integer k 3there exist a code with n = 2m-1, k − n mt and dt min + 21 where t is the error correction capability • (n,k) Reed-Solomon (RS) codes. Works with k symbols that consists of m bits that are encoded to yield code words of n symbols. For these codes m and n=2 − 1,number of check symbols n − k = 2 t dtmin =+21 • BCH and RS are popular due to large dmin, large number of codes, and easy generation
  23. k bits (n,k) n bits b. Convolutional Code encoder Một vài so sánh giữa Block code và convolutional code  (n,k) block codes: Encoder output of k input bits n bits depends only on the k input bits  (n,k,K) convolutional codes: n output bits  each source bit influences input bit n(K+1) encoder output bits  n(K+1) is the constraint length n(K+1) output bits  K is the memory depth
  24. Convolutional codes-cont’d • A Convolutional code is specified by three parameters ( n , k , K)or ( k / n, K)where –Rc = k / n is the coding rate, determining the number of data bits per coded bit. • In practice, usually k=1 is chosen and we assume that from now on. – K is the constraint length of the encoder a where the encoder has K-1 memory elements.
  25. A Rate ½ Convolutional encoder • Convolutional encoder (rate ½, K=3) – 3 bit shift-register where the first one takes the incoming data bit and the rest form the memory of the encoder. u1 First coded bit (Branch word) Input data bits Output coded bits m u1,u2 u2 Second coded bit
  26. A Rate ½ Convolutional encoder Message sequence: m = (101) Time Output Time Output (Branch word) (Branch word) u1 u1 u2 u1 u2 t t 1 1 0 0 1 1 2 0 1 0 1 0 u2 u1 u2 u1 u2 t t 3 1 0 1 0 0 4 0 1 0 1 0
  27. A Rate ½ Convolutional encoder (contd) Time Output Time Output (Branch word) (Branch word) u1 u u u u t 1 2 t 1 2 5 0 0 1 1 1 6 0 0 0 0 0 u2 m = (101) Encoder U = (11 10 00 10 11) n = 2, k = 1, K = 3, L = 3 input bits -> 10 output bits
  28. Effective code rate • Initialize the memory before encoding the first bit (all-zero) • Clear out the memory after encoding the last bit (all-zero) – Hence, a tail of zero-bits is appended to data bits. data tail Encoder codeword • Effective code rate : – L is the number of data bits and k=1 is assumed: L R = R eff n(L + K −1) c m = (101) Encoder U = (11 10 00 10 11) Example: n = 2, k = 1, K = 3, L = 3 input bits. Output = n(L + K -1) = 2*(3 + 3 – 1) = 10 output bits
  29. Encoder representation • Vector representation: – We define n binary vector with K elements (one vector for each modulo-2 adder). – The i:th element in each vector, is “1” if the i:th stage in the shift register is connected to the corresponding modulo-2 adder, and “0” otherwise. u1 g1 = (111) • Example: m u1 u2 g2 = (101) u2
  30. Encoder representation: Impulse Response • Impulse response representaiton: – The response of encoder to a single “one” bit that goes through it. Branch word • Example: Register contents u1 u2 100 1 1 Input sequence : 1 0 0 010 1 0 Output sequence : 11 10 11 001 1 1 Input m Output 1 11 10 11 0 00 00 00 1 11 10 11 Modulo-2 sum: 11 10 00 10 11
  31. Encoder representation: Polynomial • Polynomial representation: – We define n generator polynomials, one for each modulo-2 adder. Each polynomial is of degree K-1 or less and describes the connection of the shift registers to the corresponding modulo-2 adder. • Example: (1) (1) (1) 2 2 g1(X ) = g0 + g1 .X + g2 .X =1+ X + X (2) (2) (2) 2 2 g2 (X ) = g0 + g1 .X + g2 .X =1+ X The output sequence is found as follows: U(X) = m(X)g1(X) interlaced with m(X)g2 (X)
  32. Encoder representation –cont’d In more details: 2 2 3 4 m(X )g1(X ) = (1+ X )(1+ X + X ) =1+ X + X + X 2 2 4 m(X )g2 (X ) = (1+ X )(1+ X ) =1+ X 2 3 4 m(X )g1(X ) =1+ X + 0.X + X + X 2 3 4 m(X )g2 (X ) =1+ 0.X + 0.X + 0.X + X U(X ) = (1,1) + (1,0)X + (0,0)X 2 + (1,0)X 3 + (1,1)X 4 U =11 10 00 10 11
  33. State diagram • A finite-state machine only encounters a finite number of states. • State of a machine: the smallest amount of information that, together with a current input to the machine, can predict the output of the machine. K −1 • In a convolutional2 encoder, the state is represented by the content of the memory. • Hence, there are states. (grows exponentially w/ constraint length)
  34. State diagram – cont’d Current input Next output 0/00 Output state state Input (Branch word) 0 00 S0 1/11 00 0/11 00 1 11 S S 0 0 11 1/00 1 01 1 S2 00 10 01 S 0 S1 10 0/10 2 10 1 01 1/01 0/01 0 01 S3 11 11 1 10 1/10
  35. Trellis – cont’d • Trellis diagram is an extension of the state diagram that shows the passage of time. – Example of a section of trellis for the rate ½ code State Branch 0/00 S0 = 00 1/11 S2 =10 0/11 1/00 0/10 S1 = 01 1/01 0/01 S3 =11 1/10 ti ti+1 Time