Mã vòng - Cyclic codes

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

918
lượt xem 117
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mô tả Mã vòng (Cyclic Codes) là một họ mã có ứng dụng đặc biệt rộng rãi trong thông tin. Mã có tên gọi là cyclic vì do có đặc tính dịch vòng của một từ mã cũng là một từ mã. Mã vòng (hay mã chu kỳ) còn được gọi một lớp con quan trọng của mã tuyến tính. Mã này đáng chú ý vì hai lý do sau đây: - Mạch mã hoá và tính syndrome (hội chứng) có thể được thực hiện dễ dàng nhờ bộ ghi dịch có hồi tiếp (feedback connection). - Nhờ...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mã vòng - Cyclic codes

M· vßng M· vßng – Cyclic codes I/ M« t¶ M· vßng (Cyclic Codes) lµ mét hä m· cã øng dông ®Æc biÖt réng r·i trong th«ng tin. M· cã tªn gäi lµ cyclic v× do cã ®Æc tÝnh dÞch vßng cña mét tõ m· còng lµ mét tõ m·. M· vßng (hay m· chu kú) cßn ®îc gäi mét líp con quan träng cña m· tuyÕn tÝnh. M· nµy ®¸ng chó ý v× hai lý do sau ®©y: - M¹ch m· ho¸ vµ tÝnh syndrome (héi chøng) cã thÓ ®îc thùc hiÖn dÔ dµng nhê bé ghi dÞch cã håi tiÕp (feedback connection). - Nhê cÊu tróc cña m· cã thÓ t×m ®îc nhiÒu ph¬ng ph¸p ®Ó gi¶i m·. §Þnh nghÜa: Mét m· tuyÕn tÝnh C(n, k) ®îc coi lµ m· vßng nÕu mçi lÇn dÞch vßng mét tõ m· cña C th× kÕt qu¶ còng lµ mét m· vÐc t¬ cña C. Cho vÐc t¬ m· v = (v0,v1,...vn-1), c¸c thµnh phÇn cña vÐc t¬ m· nµy cã thÓ xem nh lµ hÖ sè cña ®a thøc v(x): v(x) = v0 + v1x + ... + vn-1xn-1 . VËy mçi vÐc t¬ m· v cã chiÒu dµi n t¬ng øng víi ®a thøc m· v(x) cã bËc nhá h¬n hoÆc b»ng n-1. NÕu vn-1 ≠ 0 th× bËc cña v(x) lµ n-1, nÕu vn-1 = 0 th× bËc cña v(x) nhá h¬n vn- . Sù t¬ng ®¬ng gi÷a vÐc t¬ m· v vµ ®a thøc m· v(x) lµ 1-1, v(x) ®îc gäi lµ ®a thøc m· 1 (code polynomial) cña vÐc t¬ m· v. Khi ®ã tõ vÐc t¬ m· vµ tõ ®a thøc m· ®îc sö dông nh nhau. VÝ dô: M· tuyÕn tÝnh ë b¶ng 1 ®îc goi lµ m· vßng Khèi tin VÐc t¬ m·: v §a thøc m· v(x) (0000) (0000000) 0 = 0.g(x) 1 + x +x3 = g(x) (1000) (1101000) x + x2 + x4 = x.g(x) (0100) (0110100) 1 + x2 + x3 + x4 = (1 + x).g(x) (1100) (1011100) x2 + x3 + x5 = x2.g(x) (0010) (0011010) 1 + x + x2 + x5 = (1 + x + x2).g(x) (1010) (1110010) x + x3 + x4 +x5 = (1 +x + x2).g(x) (0110) (0101110) x3 + x4 + x6 = x3.g(x) (1110) (1000110) 1 + x + x4 + x6 = (1 + x3).g(x) (0001) (0001101) x + x2 + x3 + x6 = (x + x3).g(x) (1001) (1100101) x + x2 + x6 = (1 + x + x3).g(x) (0101) (0111001) 1 + x2 + x6 = (1+ x + x3).g(x) (1101) (1010001) 1 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng x2 + x4 + x5 + x6 = (x2 + x3).g(x) (0011) (0010111) 1 + x + x2 + x3 + x4 + x5 + x6 = (1 + x2 + x3).g(x) (1011) (1111111) x + x5 + x6 = (x + x2 + x3).g(x) (0111) (0100011) 1 + x3 + x5 + x6 = (1 + x + x2 + x3).g(x) (1111) (1001011) B¶ng 1: M· vßng víi ®a thøc sinh g(x) = 1 + x + x3 Mét sè tÝnh chÊt ®¹i sè quan träng cña m· vßng: §Þnh lý 1: §a thøc m· kh¸c 0 cã bËc nhá nhÊt cña m· vßng lµ duy nhÊt. §Þnh lý 2: NÕu g(x) = g0 + g1x + ... + gr-1xr-1 + xr lµ ®a thøc m· nhá nhÊt cña m· vßng C(n, k) th× hÖ sè g0 b¾t buéc ph¶i b»ng 1. §Þnh lý 3: Cho g(x) = 1 + g1x + g2x2 + ... + xr lµ ®a thøc m· kh¸c 0 cã bËc nhá nhÊt cña m· vßng C(n, k), mét ®a thøc nhÞ ph©n cã bËc nhá h¬n hoÆc b»ng n-1 lµ ®a thøc m· nÕu vµ chØ nÕu nã lµ béi cña g(x). §Þnh lý 4: Cho m· vßng C(n,k), tån t¹i mét vµ chØ mét ®a thøc m· cã bËc n - k: g(x) = 1 + g1x + g2x2 + ... + gn-k-1xn-k-1 + xn-k. §Þnh lý 5: §a thøc sinh g(x) cña mét m· vßng C(n,k) lµ mét thõa sè cña xn+1. §Þnh lý 6: NÕu g(x) lµ ®a thøc bËc (n-k) vµ lµ mét thõa sè cña xn+1 th× g(x) sinh ra m· vßng C(n, k). 2 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng II/ Ma trËn sinh vµ ma trËn kiÓm tra cña m· vßng. Gäi g(x) lµ ®a thøc sinh bËc n-k cña m· vßng C(n,k). Mét khèi d÷ liÖu k phÇn tö (m0, m1,... mk-1) cã thÓ ®îc xem lµ mét ®a thøc th«ng tin: m(x) = m0 + m1x + ... + mk-1xk-1. ViÖc m· ho¸ th«ng qua viÖc nh©n ®a thøc th«ng tin víi ®a thøc sinh. KÕt qu¶ ta cã: Cm = (c0, c1, ... cn-1) Cm(x) = m(x).g(x) = c0 + c1.x + ... + cn-1.xn-1 TÝch ®a thøc trªn ®îc biÓu diÔn díi d¹ng tÝch ma trËn nh: Cm(x) = m(x).g(x) = (m0 + m1.x + ... + mk-1.xk-1).g(x) = m0.g(x) + m1.x.g(x) + ... + mk-1.xk-1.g(x) g(x) x.g(x) = [m0 + m1.x + ... + mk-1.xk-1]. . . xk-1.g(x) D¹ng tæng qu¸t cña ma trËn sinh G cña m· vßng C(n,k) lµ: g0 g1 g2 ... ... ... ... gn-k 0 0 ... 0 0 g0 g1 ... ... ... ... ... gn-k 0 ... 0 G= 0 0 g0 gn-k ... 0 .. .. .. .. .. .. .. .. .. .. .. .. 000 .. 0 g0 gn-k ( víi g0 = gn-k = 1) Trêng hîp tæng qu¸t G kh«ng cã d¹ng hÖ thèng. Tuy nhiªn cã thÓ chuyÓn G vÒ d¹ng hÖ thèng b»ng phÐp biÕn ®æi hµng cña ma trËn. VÝ dô: XÐt m· vßng C(7, 4) cho ë b¶ng 1 víi ®a thøc sinh g(x) = 1 + x + x3 cã ma trËn nh sau: 1101000 G= 0110100 0011010 0001101 Ta thÊy G kh«ng cã d¹ng hÖ thèng. Nhng nÕu dïng phÐp biÕn ®æi hµng: h3 = h3 + h1 vµ h4 = h4 + h1 + h2 ta thu ®îc Ma trËn G’ cã d¹ng hÖ thèng nh sau: 3 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng 1101000 G’ = 0110100 1110010 1010001 Víi g(x) lµ thõa sè cña xn + 1, cã: xn + 1 = g(x).h(x) Víi ®a thøc h(x) cã bËc lµ k ®îc biÓu diÔn nh sau: h(x) = h0 + h1.x + ... + hk.xk, (víi h0 = hk = 1) Cho v = (v0, v1,... vn-1) lµ vÐc t¬ m· cña C. Khi ®ã v(x) = m(x).g(x). Nh©n v(x) víi h(x) ta ®îc: v(x).h(x) = a(x).g(x).h(x) = a(x).(xn + 1) = a(x) + xn.a(x) Do bËc cña v(x) nhá h¬n hoÆc b»ng k-1 nªn c¸c gi¸ trÞ cña xk, xk+1, ...xn-1 kh«ng cã trong biÓu thøc m(x) + xk.m(x). NÕu khai triÓn kÕt qu¶ v(x).h(x) th× hÖ sè xk, xk+1,... xn ph¶i b»ng 0. Do ®ã nhËn ®îc n-k ph¬ng tr×nh sau: ∑hivn-i-j = 0, víi i ≤ j ≤ n-k. Hµm sè ngîc cña h(x) lµ: x k.h(x-1) = hk + hk-1x + hk-2x2 + ... + h0xk DÔ dµng nhËn thÊy r»ng xkh(x-1) còng lµ thõa sè cña (xn + 1). VËy ®a thøc sinh xkh(x-1) sinh ra m· vßng (n,n-k) víi ma trËn H(n-k) x n lµ ma trËn sinh: hk hk-1 hk-2 ..... h0 0 .... 0 0 hk hk-1 hk-2 ... h0 .... 0 H= 0 0 hk hk-1 hk-2 .... h0... 0 ... 0 0 ...0 hk hk-1 hk-2 ... h0 BÊt kú vÐc t¬ m· nµo cña C ®Òu trùc giao víi mçi hµng cña H. Do ®ã H lµ ma trËn kiÓm tra ch½n lÎ cña m· vßng C. Do H nhËn ®îc tï ®a thøc h(x) nªn h(x) ®îc gäi lµ ®a thøc kiÓm tra cña C. §Þnh lý 7: Gäi C lµ m· vßng (n,k) víi ®a thøc sinh g(x). M· ®èi ngÉu cña C còng lµ m· vßng vµ ®îc sinh ra bëi ®a thøc: xk.h(x-1) víi h(x) = (xn + 1)/g(x). 4 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng III/ M· ho¸ m· vßng M· ho¸ m· vßng (n,k) d¹ng hÖ thèng gåm ba bíc: Bíc 1: Nh©n ®a thøc th«ng tin u(x) víi xn-k. Bíc 2: Chia xn-k.u(x) cho g(x) nhËn ®îc phÇn d b(x). Bíc 3: H×nh thµnh tõ m· b(x) + xn-k.u(x). TÊt c¶ ba bíc nµy cã thÓ thùc hiÖn b»ng m¹ch chia víi thanh ghi dÞch n-k tÇng cã hµm håi tiÕp t¬ng øng víi ®a thøc sinh g(x): g(x) = 1 + g1x + g2x2 +... + gn-k-1xn-k-1 + xn-k. S¬ ®å m· ho¸ ®îc chØ trong h×nh 1 Quy íc: Lµ mét kh©u cña thanh ghi dÞch (flip-flop) Cæng céng modul-2 (XOR) Mèi liªn kÕt (g = 0: kh«ng cã sù liªn kÕt, g = 1 cã sù liªn kÕt) Cæng g1 g2 gn-k-1 g0=1 b0 b1 b2 bn-k-1 Th«ng tin xn-k.u(x) Tõ m· H×nh 1: M¹ch m· ho¸ vßng (n,k) víi ®a thøc sinh: C¸c sè kiÓm tra ch½n lÎ 2 n-k-1 n-k g(x) = 1 + g1.x + g2.x + ... + gn-k-1.x +x C¸c bíc t¹o m· dïng ®a thøc sinh nh sau: Bíc 1: Cæng ®ãng (cho th«ng tin qua), k ch÷ sè th«ng tin: u0, u1,... uk-1 (hay ë d¹ng ®a thøc lµ: u(x) = u0 + u1x + u2x2 + ... + uk-1xk-1) ®îc dÞch vµo m¹ng vµ ®ßng thêi nèi vµo kªnh truyÒn. DÞch th«ng tin u(x) vµo m¹ch tõ thiÕt bÞ ®Çu cuèi ®Ó nh©n tríc u(x) víi xn-k. Ngay sau khi th«ng tin ®îc ®a vµo m¹ch th× n - k ch÷ sè cßn l¹i trong thanh ghi lµ nh÷ng sè kiÓm tra ch½n lÎ. 5 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng Bíc 2: C¾t ®øt ®êng håi tiÕp b»ng c¸ch ®iÒu khiÓn cho c¸c cæng gi (hë kh«ng cho th«ng tin qua). Bíc 3: DÞch nh÷ng con sè kiÓm tra ch½n lÎ vµ ®a ra ®êng truyÒn. C¸c ch÷ sè kiÓm tra nµy kÕt hîp víi k chc sè th«ng tin t¹o thµnh vÐc t¬ m·. VÝ dô: XÐt mét m¹ch m· ho¸ m· vßng (7,4) víi ®a thøc sinh g(x) = 1 + x + x3 nh Cæng h×nh 2 g1 g0=1 b0 b1 b2 Th«ng tin xn-k.u(x) Tõ m· C¸c sè kiÓm tra ch½n lÎ H×nh 2: M¹ch m· ho¸ m· vßng (n = 7, k = 4) víi ®a thøc sinh g(x) = 1 + x + x3 ViÖc m· ho¸ m· vßng còng cã thÓ thùc hiÖn b»ng c¸ch sö dông ®a thøc kiÓm tra ch½n lÎ h(x) = h0 + h1.x + ... + hk.xk. Cã thÓ coi c«ng thøc: Vn-k-j = ∑hivn-i-j = 0 , víi i ≤ j ≤ n-k lµ luËt ®Ó x¸c ®Þnh n-k ch÷ sè kiÓm tra ch½n lÎ v0, v1,... vn-k-1. H×nh 3 lµ m¹ch m· ho¸ cã hÖ sè h(x) lµ c¸c kÕt nèi håi tiÕp. Nguyªn lý ho¹t ®éng cña m¹ch vµ c¸c bíc m· hãa dïng ®a thøc kiÓm tra nh sau: Bíc 1: Cæng 1 ®ãng, cæng 2 hë, k ch÷ sè th«ng tin u(x) = u0 + u1x + ... +uk-1xk-1 ®îc dÞch vµo thanh ghi ®ång thêi truyÒn ra kªnh th«ng tin. Bíc 2: Ngay sau khi toµn bé c¸c ch÷ sè th«ng tin ®îc dÞch vµo thanh ghi. Cæng 1 hë, cæng 2 ®ãng, ch÷ sè kiÓm tra ®Çu tiªn lµ: Vn-k-1 = h0.vn-1 + h1.vn-2 + ... + hk-1.vn-k uk-1 + h1.uk-2 + ...+ hk-1.u0 Vn-k-1 ®îc t¹o thµnh vµ xuÊt hiÖn t¹i ®iÓm P. Bíc 3: Thanh ghi dÞch vßng mét bit, ch÷ sè kiÓm tra ®îc dÞch vµo kªnh th«ng tin vµ ®ång thêi còng dÞch vµo thannh ghi, ch÷ sè kiÓm tra thø hai lµ: Vn-k-2 = h0.vn-2 + h1.vn-3 + .... + hk-1.vn-k = uk-2 + h1.uk-3 + ... + hk-2.u0 + hk-1.un-k-1. Vn-k-2 ®îc t¹o thµnh vµ xuÊt hiÖn t¹i diÓm P. 6 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng Bíc 4: LÆp l¹i bíc 3 cho ®Õn khi n-k ch÷ sè kiÓm tra ®îc t¹o ra vµ dÞch vµo kªnh th«ng tin. hk-1 hk-2 h2 h0 Cæng2 h0=1 §Çu vµo Cæng1 Vn-k Vn-(k-1) Vn-2 Vn-1 P §Çu ra: Vn-k-1, Vn-k-2,.. H×nh 3: M¹ch m· ho¸ m· vßng (n, k) dùa vµo ®a thøc kiÓm tra h(x) = 1 + h1.x + ... + xk §Ó minh ho¹, xÐt vÝ dô sau: H×nh 4 lµ s¬ ®å m· ho¸ cho m· vßng (7,4) cã ®a thøc sinh g(x) = 1 + x + x3 dùa vµo ®a thøc kiÓm tra: h(x) = x7/1 + x + x3 = 1 + x + x2 + x4 Mçi tõ m· cã d¹ng v = (v0, v1, v2, v3, v4, v5, v6) víi v3, v4, v5, v6 lµ nh÷ng con sè cña th«ng tin, cßn v0, v1, v2 lµ nh÷ng con sè kiÓm tra ch½n lÎ (parity), ph¬ng tr×nh x¸c ®Þnh bëi nh÷ng con sè kiÓm tra lµ: V3-j = 1.v7-j + 1.v6-j + 1.v5-j + 0.v4-j = v7-j + v6-j + v5-j, víi 1 ≤ j ≤ 3 Gi¶ sö th«ng tin cÇn m· ho¸ lµ (1011) th×: v3 = 1, v4 = 0, v5 = 1, v6 = 1. Ch÷ sè kiÓm tra ®Çu tiªn lµ: v2 = v6 + v5 + v4 = 1 + 1 + 0 = 0 Ch÷ sè kiÓm tra thø hai lµ: v1 = v5 + v4 + v3 = 1 + 0 + 1 Ch÷ sè kiÓm tra thø ba lµ: v0 = v4 + v3 + v2 = 0 + 1 + 0 = 1 V× vËy tõ m· t¬ng øng víi th«ng tin (1011) lµ (1001011) Cæng2 h2=1 h1=1 h0=1 §Çu vµo Cæng1 P §Çu ra: 1001011 H×nh 4: M¹ch m· ho¸ vßng (n=7, k=4) dùa vµo ®a thøc kiÓm tra h(x) = 1 + x + x2 + x4 7 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng IV/ Gi¶i m· vßng ViÖc gi¶i m· vßng bao gåm ba bíc nh viÖc gi¶i m· khèi tuyÕn tÝnh: Bíc 1: TÝnh Syndrome. Bíc 2: Dùa vµo syndrome ®Ó x¸c ®Þnh vÐct¬ lçi. Bíc 3: Söa lçi, thùc hiÖn phÐp céng modul-2 gi÷a vÐct¬ lçi vµ vÐct¬ nhËn ®îc. KÕt qu¶ lµ vÐct¬ th«ng tin thùc sù ®îc truyÒn ®i. NÕu söa tuÇn tù tõng bit mét th× chØ cÇn mét cæng XOR. Ngîc l¹i nÕu thùc hiÖn mét c¸ch söa song song th× ph¶i dïng n cæng XOR. CÊu tróc m· vßng cho phÐp gi¶i m· vÐct¬ nhËn r(x) = r0 + r1x + r2x2+ .... + rn-1xn-1 mét c¸ch tuÇn tù. Nh÷ng bit nhËn ®îc sÏ ®îc gi¶i m· lÇn lît bëi cïng mét m¹ch gi¶i m·. Ngay sau khi tÝnh syndrom. M¹ch gi¶i m· kiÓm tra sù t¬ng øng cña syndrome s(x) víi vÐct¬ söa ®îc e(x) = e0 + e1x + e2x2 +... +en-1xn-1 víi mét lçi sai ë vÞ trÝ cao nhÊt xn-1 (en-1 = 1). NÕu s(x) kh«ng cã sai ë vÞ trÝ bËc cao nhÊt (en-1≠0) th× lu gi÷ trong thanh ghi ®Öm (buffer register) vµ ®ång thêi thanh ghi sundrome dÞch ®i mét lÇn. B»ng c¸ch nµy, r(1)(x) = r0x + r1x2 + ... + rn-2xn-1 vµ ®a thøc syndrome míi cña r(1)(x) lµ s(1)(x). Lóc ®ã bit thø hai rn-2 cña r(x) trë thµnh bit thø nhÊt cña r(1)(x). M¹ch gi¶i m· t¬ng tù sÏ kiÓm tra s(i)(x) cã t¬ng ®¬ng víi vÐct¬ sai sè víi lçi t¹i vÞ trÝ xn-1 hay kh«ng. NÕu syndrome s(x) cña r(x) t¬ng øng víi mét vÐct¬ sai víi lçi sai ë vÞ trÝ xn-1 th× bit ®Çu tiªn nhËn ®îc rn-1 lµ bit sai vµ nã ph¶i ®îc söa cho ®óng. ViÖc söa sau ®îc thùc hiÖn qua viÖc tÝnh tæng rn-1⊕en-1. §a thøc söa lçi lµ: r1(x) = r0 + r1x + r2x2 + ... + rn-2xn-1 + (rn-1⊕en-1)xn-1. Sau ®ã lçi sai ë bit en-1 ®îc xo¸ bá khái syndrome s(x). ViÖc nµy thùc hiÖn b»ng viÖc céng modul syndrome cña e’(x) = xn-1 víi s(x). KÕt qu¶ céng nµy lµ ®a thøc ®· söa sai r1(x). TiÕp theo dÞch vßng r1(x) vµ ®ång thêi dÞch vßng thanh ghi syndrome. KÕt qu¶ viÖc dÞch vßng thu ®îc r1(1)(x) = (rn-1⊕en-1) + r0x + ...+ rn-2xn-1 V× thÕ nÕu 1 ®îc thªm vµo tËn cïngbªn tr¸i cña thanh ghi sundrome trong khi dÞch vßng th× thu ®îc s1(1)(x). M¹ch gi¶i m· b¾t ®Çu gi¶i nh÷ng bit nhËn ®îc rn-2. ViÖc gi¶i m· rn-2 vµ c¸c lo¹i bit cßn l¹i ®Òu ®îc tÝnh gièng nh gi¶i m· rn-1. Khi mét lçi ®îc ph¸t hiÖn vµ söa, nã sÏ lµ cho syndrome thay ®æi. Qu¸ tr×nh gi¶i m· sÏ ngõng sau n lÇn dÞch vßng. NÕu e(x) lµ vÐct¬ lçi ®· ®îc söa th× thanh ghi syndrome sÏ b»ng 0. KÕt thóc qu¸ tringhf gi¶i m· sÏ nhËn ®îc r(x) ®îc gi¶i m· chÝnh x¸c. NÕu kÕt thóc qu¸ tr×nh gi¶i m· mµ syndrome kh¸c 0 th× lçi sai ®îc ph¸t hiÖn vµ kh«ng söa sai ®îc. Bé gi¶i m· vßng (n,k) cã s¬ ®å nh h×nh 5 gåm c¸c khèi: 8 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng - Thanh ghi syndrome. - Bé ph¸t hiÖn vÐct¬ lçi. - Thanh ghi ®Öm lu gi÷ vÐct¬ nhËn. Cæng2 r1 Cæng1 Thanh ghi dÖm VÐct¬ ®îc söa Cæng1 Cæng sai Thanh ghi syndrome ei Thanh ghi syndrome Cæng ChØnh syndrome H×nh 5: Bé m· vßng víi ®a thøc nhËn ®îc ë ®Çu thu r(x) ®îc dÞch vµo thanh ghi syndrome tõ bªn tr¸i. Thñ tôc söa lçi ®îc m« t¶ nh sau: Bíc 1: Syndrome ®îc t¹o ra b»ng c¸ch dich toµn bé vÐct¬ nhËn vµo thanh ghi syndrome vµ thanh ghi dÖm. Bíc 2: Bé ph¸t hiÖn sai lµ m¹ch logic ®îc thiÕt kÕ sao cho ®Çu ra cña nã lµ 1 khi vµ chØ khi syndrome trong thanh ghi syndrome t¬ng øng víi vÐct¬ sai cã thÓ söa ®îc mét lçi t¹i bit bËc cao nhÊt xn-1. Do ®ã nÕu bit 1 xuÊt hiÖn ë ®Çu ra cña m¹ch ph¸t hiÖn sai th× bit nhËn ®îc lµ bit sai ph¶i söa, nÕu bit 0 xuÊt hiÖn th× bit nhËn ®îc lµ ®óng lµ kh«ng ph¶i söa. Bíc 3: Bit ®Çu tiªn ®îc dÞch ra khái thanh ghi ®Öm. Cïng lóc ®ã thanh ghi syndrome còng dÞch mét bit. NÕu ký hiÖu võa ®äc ra lµ sai th× sÏ ®îc söa vµ ë ®Çu ra sÏ nhËn ®îc ký hiÖu ®óng. §Çu ra ë m¹ch ph¸t hiÖn sai còng ®îc m¾c håi tiÕp vµo thanh ghi syndrome. KÕt qu¶ cã mét syndrome t¬ng øng víi vÐct¬ nhËn ®· dÞch vÒ bªn ph¶i. Bíc 4: Syndrome míi nhËn ®îc ë bíc 3 sÏ dïng ®Ó ph¸t hiÖn sai ë ký hiÖu kÕ tiÕp s¾p ®îc ®äc ra khái thanh ghi ®Öm. M¹ch gi¶i m· lÆp l¹i ë bíc 2 vµ 3. Bíc 5: M¹ch gi¶i m· sÏ gi¶i m· lÇn lît tõng ký hiÖu theo c¸ch trªn cho ®Õn khi toµn bé vÐct¬ nhËn r ®îc ®äc ra khái thanh ghi ®Öm. Sau khi toµn bé vÐct¬ r ®äc ra khái thanh ghi ®Öm: nÕu thanh ghi syndrome chøa toµn 0 nghÜa lµ vÐct¬ lçi ®îc ph¸t hiÖn vµ söa ®óng. 9 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng VÝ dô: Cho m· vßng (7, 4) víi ma trËn sinh g(x) = 1 + x + x3. M· nµy cã kho¶ng c¸ch Hamming nhá nhÊt lµ 3 vµ do vËy cã kh¶ n¨ng söa lçi ®¬n. Gi¶ sö chuçi nhËn r(x) = r0 + r1x + r2x2 + r3x3 + r4x4 + r5x5 + r6x6 ®îc dÞch vµo thanh ghi syndrome tõ sang tr¸i. B¶ng vÐct¬ lçi vµ c¸c syndrome t¬ng øng cña chóng ®îc kª ë b¶ng 2: VÐct¬ lçi Syndrome VÐct¬ syndrome e(x) s(x) (s0, s1, s2) e6(x) = x6 s(x) = 1 + x2 101 e5(x) = x5 s(x) = 1 + x + x2 111 e4(x) = x4 s(x) = x + x2 011 e3(x) = x3 s(x) = 1 + x 110 e2(x) = x2 s(x) = x2 001 e1(x) = x1 s(x) = x 010 e0(x) = x0 s(x) = 1 100 B¶ng 2: VÐc t¬ lçi vµ c¸c syndrome t¬ng øng víi ®a thøc nhËn ®îc chuyÓn vµo thanh ghi syndrome tõ tr¸i sang ph¶i. Syndrome s(x) ®îc tÝnh b»ng c¸ch lÊy phÇn d c¶u phÐp chia xi cho g(x). Tõ ®ã suy ra vÐct¬ syndrome t¬ng øng. Gi¶ sö r»ng mét lçi ®¬n xuÊt hiÖn ë vÞ trÝ xi. Sau khi chuçi nhËp ®îc dÞc vµo thanh ghi syndrome. Syndrome trong danh s¸ch ghi sÏ lµ (101). Tuy nhiªn sau (6-i) lÇn dÞch th× néi dung cña thanh ghi kh«ng ph¶i lµ (101). V× thÕ cÇn söa lçi syndrome (101). Mét m¹ch gi¶i m· hoµn chØnh ®îc vÏ nh h×nh 6: 10 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng §Çu vµo Bé dån kªnh §Çu ra r(x) Cæng Cæng Cæng H×nh 6: M¹ch gi¶i m· cho m· vßng (7,4) víi ®a thøc sinh g(x) = 1 + x + x2 Miªu t¶ qu¸ tr×nh gi¶i m· nh sau: Gi¶ sö vÐct¬ m· v = (1001011) ®îc truyÒn thµnh vÐct¬ nhËn r = (1011011). Mçi lçi ®¬n xuÊt hiÖn ë vÞ trÝ x2. Khi nhËp ®îc dÞch vµo thanh ghi ®Öm vµ thanh ghi syndrome. Thanh ghi syndrome chøa gi¸ trÞ (001). Ë h×nh díi ®©y lµ m« t¶ qu¸ tr×nh ghi dÞch trªn c¸c thanh ghi ®Öm vµ thanh ghi syndrome. Sau 4 lÇn dÞch néi dung cña thanh ghi syndrome lµ (101) vµ mÉu lçi r2 sÏ lµ sè kÕ tiÕp xuÊt khái thanh ghi ®Öm. Nhîc ®iÓm cña m¹ch gi¶i m· h×nh 6 lµ thêi gian gi¶i m· l©u do ph¶i dÞch vßng tõng bit mét. Bé gi¶i m· nh trªn ®îc gäi lµ bé gi¶i m· Meggit. ë bé gi¶i m· nµy tõ m· ®îc ®a vµo vÞ trÝ bËc cao nhÊt ®Õn vÞ trÝ thÊp nhÊt vµ khi dÞch vßng c¶ thanh ghi ®Öm vµ thanh ghi syndrome ®ªï dÞch vßng sang ph¶i: Bé gi¶i m· Meggit còng cã thÓ gi¶i m· ngîc, nghÜa lµ nã sÏ gi¶i m· tõ vÞ trÝ bËc thÊp nhÊt ®Õn bËc cao nhÊt. Khi ®ã, thanh ghi ®Öm vµ thanh ghi syndrome sÏ dÞch sang tr¸i. 11 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com
M· vßng Qu¸ tr×nh söa sai cña m¹ch ®îc m« t¶ nh trªn h×nh vÏ dìi ®©y: 0 B¾t ®Çu 0 0 1 1 0 1 1 0 1 1 0 LÇn dÞch 1 0 0 1 1 0 1 1 0 1 Thø1 0 LÇn dÞch 0 1 1 1 1 1 0 1 1 0 Thø 2 0 LÇn dÞch 1 1 1 0 1 1 1 0 1 1 Thø 3 0 LÇn dÞch 1 0 1 1 0 1 1 1 0 1 Thø 4 0 LÇn dÞch 0 0 0 0 1 0 1 1 1 0 Thø 5 0 LÇn dÞch 0 0 0 0 0 1 0 1 1 1 Thø 6 0 LÇn dÞch 0 0 0 1 0 0 1 0 1 1 Thø7 VÒ nguyªn t¾c, ph¬ng ph¸p gi¶i m· Meggit cã thÓ ¸p dông víi bÊt kú m· nµo, nhng trong thùc tÕ m¹ch gi¶i m· rÊt phøc t¹p v× vËy cßn nhiÒu ph¬ng ph¸p gi¶i m· kh¸c ®· ®îc ph¸t minh, chóng lµ c¸c d¹ng biÕn thÓ tõ ph¬ng ph¸p gi¶i m· Meggit nh lµ: gi¶i m· b»ng ph¬ng ph¸p bÉy lçi, ph¬ng ph¸p gi¶i m· bÉy lçi c¶i tiÕn... tuú theo tõng trêng hîp cô thÓ mµ cã thÓ sö dông mét m¹ch gi¶i m· hoÆc kÕt hîp nhiÒu m¹ch gi¶i m· nh»m ®¶m b¶o tèt yªu cÇu cña tõng nhiÖm vô ®Æt ra. 12 Hoµng ChiÕn Th¾ng - §HKTCN Th¸i Nguyªn Email: ht.destiny@gmail.com