Download miễn phí Mã vòng – Cyclic Codes



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áchsửa songsong thì phảidùng ncổng XOR


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2014-06-04-ma_vong_cyclic_codes.A5P1AThTOy.swf /tai-lieu/de-tai-ung-dung-tren-liketly-69122/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

Mã vòng
Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 1
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-1x
n-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
hay 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-
1. 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ã
(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)
(1000) (1101000) 1 + x +x3 = g(x)
(0100) (0110100) x + x2 + x4 = x.g(x)
(1100) (1011100) 1 + x2 + x3 + x4 = (1 + x).g(x)
(0010) (0011010) x2 + x3 + x5 = x2.g(x)
(1010) (1110010) 1 + x + x2 + x5 = (1 + x + x2).g(x)
(0110) (0101110) x + x3 + x4 +x5 = (1 +x + x2).g(x)
(1110) (1000110) x3 + x4 + x6 = x3.g(x)
(0001) (0001101) 1 + x + x4 + x6 = (1 + x3).g(x)
(1001) (1100101) x + x2 + x3 + x6 = (x + x3).g(x)
(0101) (0111001) x + x2 + x6 = (1 + x + x3).g(x)
(1101) (1010001) 1 + x2 + x6 = (1+ x + x3).g(x)
Mã vòng
Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 2
(0011) (0010111) x2 + x4 + x5 + x6 = (x2 + x3).g(x)
(1011) (1111111) 1 + x + x2 + x3 + x4 + x5 + x6 = (1 + x2 + x3).g(x)
(0111) (0100011) x + x5 + x6 = (x + x2 + x3).g(x)
(1111) (1001011) 1 + x3 + x5 + x6 = (1 + x + x2 + x3).g(x)
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-1x
r-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 + g2x
2 + ... + 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 hay 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 + g2x
2 + ... + gn-k-1x
n-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).
Mã vòng
Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 3
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-1x
k-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.x
n-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.x
k-1).g(x)
= m0.g(x) + m1.x.g(x) + ... + mk-1.x
k-1.g(x)
g(x)
x.g(x)
= [m0 + m1.x + ... + mk-1.x
k-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
.. .. .. .. .. .. .. .. .. .. .. ..
0 0 0 .. 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:
1 1 0 1 0 0 0
G = 0 1 1 0 1 0 0
0 0 1 1 0 1 0
0 0 0 1 1 0 1
Ta thấy G không có dạng hệ thống.
Nhưng 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:
Mã vòng
Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 4
1 1 0 1 0 0 0
G’ = 0 1 1 0 1 0 0
1 1 1 0 0 1 0
1 0 1 0 0 0 1
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.x
k, (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 hay 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-2x
2 + ... + h0x
k
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:
h k 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).
Mã vòng
Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 5
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 + g2x
2 +... + gn-k-1x
n-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)
Hình 1: Mạch mã hoá vòng (n,k) với đa thức sinh:
g(x) = 1 + g1.x + g2.x
2 + ... + gn-k-1.x
n-k-1 + xn-k
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 + u2x
2 + ... + uk-1x
k-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ẻ.
b0 bn-k-1 b2 b1
Cổng
g0=1
g1 g2 gn-k-1
Thông tin xn-k.u(x)
Các số kiểm tra
chẵn lẻ
Từ mã
Mã vòng
Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 6
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...

---