Xem mẫu
- Họ và tên: Nguyễn Quốc Thưởng
MSSV: 0820168
Lớp: 08ĐVT01
Môn học: TRUYỀN THÔNG SỐ
Đề tài: TÌM HIỂU VỀ MÃ VÒNG
I – Giới thiệu:
1. Định nghĩa: Một mã tuyến tính C(n,k) được gọi là mã vòng n ếu ta d ịch
một vòng từ mã thì kết quả cũng là một từ mã. Tức là w= là m ột t ừ mã thì
v= cũng là một từ mã.
- Đa thức mã: Nếu w= là một từ mã thì đa thức w= là đa thức mã tương ứng
với từ mã w.
*Chú ý: Ta sử dụng đa thức mã để chứng minh các tính chất của mã vòng.
- Gọi là từ mã do dịch từ mã w i bit và là đa thức mã tương ứng của Các từ
mã được xét trên trường GF(2) – trường nhị phân.
- Trên trường GF(2) ta có:
Xét ví dụ sau:
-
i
0 1001000
1 0100100
2 0010010
3 0001001
4 1000100
5 0100010
6 0010001
Từ ví dụ trên ta rút ra được mối quan hệ giữa với :
2. Các tính chất của mã vòng:
a. Tính chất 1: Đa thức mã khác 0 có bậc nhỏ nhất là duy nhất.
Chứng minh: Giả sử tồn tại 2 đa thức mã khác 0 và có cùng bậc nhỏ
nhất là r(0 < r < n).
Ta xét đa thức mã: , lúc này có bậc t ối đa là r-1. Điều này mâu thuẫn với
giả thiết r là bậc nhỏ nhất nên ta có điều phải chứng minh.
Từ đây, ta kí hiệu đa thức mã có bậc nhỏ nhất là
b. Tính chất 2: Hệ số tự do của phải bằng 1.
Chứng minh: Giả sử . Ta có:
- Ta đặt . Rõ ràng cũng là một đa th ức mã có đ ược nh ờ d ịch trái 1 bit
hay dịch phải (n-1) bit từ đa thức mã . Mặt khác, có bậc r-1, điều này
mâu thuẫn với giả thiết bậc của là r. Đến đây ta đã có đi ều ph ải ch ứng
minh.
c. Tính chất 3: Một đa thức trên trường GF(2) có bậc là đa th ức mã n ếu
và chỉ nếu nó là bội số của Tức là .
Chứng minh:
Chứng minh nếu và bậc của nhỏ hơn hoặc bằng n-1 thì là đa
thức mã:
Ta có:
Trong đó p là bậc của và . Mà do với là đa th ức mã (t ương ứng v ới t ừ
mã ) dịch i bit). Nên là đa thức mã vì bằng với 1 t ổ h ợp tuy ến tính c ủa
các đa thức mã.
Để chứng minh chiều ngược lại của mệnh đề ta chia chúng ta
được:
Trong đó là đa thức dư và có bậc nhỏ hơn bậc của . Mặt khác, đối
với các đa thức trên trường GF(2) ta có thể suy ra:
Nên là một đa thức mã. Do định nghĩa là đa thức có bậc nhỏ nh ất
nên ta suy ra (Điều phải chứng minh).
Từ tính chất này, ta gọi là đa thức sinh vì từ có thể sinh ra tất cả
các đa thức mã khác.
d. Tính chất 4: Đa thức sinh của một mã vòng C(n,k) có bậc r=n-k.
Chứng minh: Theo định lí trên ta có mỗi đa thức mã là 1 b ội sô c ủa . Vì
vậy có bao nhiêu từ mã thì có bấy nhiêu đa thức . Trước hết chúng ta
thấy do bậc của nên bậc của Do đó có tổng cộng đa th ức . M ặt khác,
số lượng từ mã là . Từ đây suy ra
Từ đây ta biểu diễn như sau:
(với )
e. Tính chất 5: Đa thức sinh của 1 mã vòng C(n,k) là 1 ước số của .
Chứng minh: Ta có:
Chọn i=k, vì bậc nên ta suy ra tức là:
- Vì là 1 đa thức mã nên có thể viết: . Thế vào phương trình trên ta có
điều phải chứng minh.
f. Tính chất 6: Nếu là 1 đa thức có bậc n-k và là ước số c ủa thì sinh ra
mã vòng C(n,k).
Chứng minh: Xét k đa thức . Các đa thức này đều có b ậc nh ỏ h ơn ho ặc
bằng n-1. Gọi v(x) là 1 tổ hợp tuyến tính của k đa th ức này v ới các h ệ
số
v(x) là 1 đa thức có bậc nhỏ hơn hoặc bằng n-1 và là bội số của . Có tất
cả đa thức khác nhau và tạo nên 1 không gian tuy ến tính c ủa các đa
thức mã với là các đa thức hàm cơ sở. Vì vậy tổ hợp tương ứng với
đa thức này tạo nên 1 mã tuyến tính C(n,k). Bây gi ờ chúng ta ch ứng
minh mã này có tính vòng, tức là chứng minh nếu v là 1 t ừ mã thì d ịch v
1 bit chúng ta được cũng là 1 từ mã. Ta biểu diễn:
Ta lại có
Do đều là bội của nên cũng là bội của . Vì v ậy cũng là 1 đa
thức mã.
3. Ma trận sinh và ma trận kiểm tra của mã vòng:
a. Ma trận sinh của mã vòng:
Ma trận sinh của mã vòng C(n,k) có dạng
Trong đó, .
Ví dụ: Tìm 1 mã vòng trong C(7,4). Dựa vào các tính ch ất c ủa mã vòng
ta biết được đa thức sinh của mã có bậc là 3 và là ước s ố của . Ta phân
tích: . Có 2 đa thức cùng có bậc là 3, chẳng hạn ta chọn . Từ đây ta có
ma trận sinh
- Bằng cách thực hiện các biến đổi đại số tuyến tính ta có thể biến đổi
thành ma trận sinh hệ thống dạng 2 như sau
Dịch chuyển 4 bit ta được ma trân sinh hệ thống dạng 1:
b. Mã hóa thành từ mã hệ thống:
Gọi u(x) là đa thức tương ứng với thông báo u. Bậc của u(x) nhỏ hơn
hoặc bằng k-1. Chia cho g(x) ta được
Trong trường GF(2) ta suy ra được
Vì là bội của g(x) nên nó là đa thức mã. Đa thức mã này có k bit sau là k
bit thông báo, đó chính là từ mã hệ thống dạng 2 tương ứng với thông
báo u.
Ví dụ: Cho mã vòng C(7,4) có ma trận sinh . Thông báo u=1011, ta mã
hóa u thành từ mã hệ thống dạng 2 như sau:
Ta có: . Nhân với rồi chia cho g(x) ta được
w=0011010 là từ mã hệ thống dạng 2 tương ứng của u.
c. Ma trận kiểm tra mã vòng:
- Ta có thể kiểm tra từ ma trận sinh hoặc ma trận sinh h ệ thống. Ngoài
ra, đối với mã vòng chung ta có một cách xác đ ịnh ma tr ận ki ểm tra
nhanh chóng hơn.
Ta có thể đặt:
Ta gọi là đa thức đối ngẫu của . Do có bậc k nên ta có thể biểu diễn:
Gọi là đa thức mã tương ứng với từ mã . Chúng ta có th ể bi ểu di ễn
như sau trong có bậc nhỏ hơn hoặc bằng k-1
=>
Do có bậc nhỏ hơn hoặc bằng k-1 nên từ đây chúng ta suy ra các h ệ số
của trong bằng 0. Từ đó ta suy ra được các đẳng thức sau:
…
Từ các đẳng thức này ta suy ra tích các vecto sau bằng 0:
…
Ta đặt
Thì => H là ma trận kiểm tra mã vòng.
Ví dụ: Cho mã vòng C(7,4) có ma trận sinh là . Tìm ma trận kiểm tra H.
Giải: Từ g(x) ta suy ra . Ma trận kiểm tra
- II – Các loại mã vòng:
Loại mã vòng được ứng dụng rất rộng rãi là mã BCH. Mã BCH có
tên viết tắt của 3 người sáng lập ra nó là Bose, Chaduhuri và
Hocquenghem, nó là một loại mã sửa lỗi vòng ngẫu nhiên quan trọng,
có khả năng sửa được nhiều lỗi. Trong BCH có 2 lớp con là mã BCH
nhị phân và mã BCH không nhị phân (Mã Reed - Solomon). Ta sẽ tìm
hiểu về 2 loại mã này.
1. Mã BCH nhị phân:
- Xây dựng 1 mã BCH nhị phân gồm các thông số sau:
Độ dài từ mã:
Số bit kiểm tra:
Khoảng cách Hamming:
Tìm ma trận kiểm tra và đa thức sinh ta sử dụng định lí sau:
Cho a là một phần tử của trường có đa thức tối thi ểu là 1 đa th ức
căn bản bậc m. Thì mã có ma trận sau làm ma trận ki ểm tra là 1 mã
vòng có khoảng cách Hamming lớn hơn hoặc bằng 2t+1, trong đó mỗi
phần tử trong ma trận bên dưới được thay thế bằng vecto m thành
phần tương ứng của nó.
Đa thức sinh của bộ mã là đa thức bội số chung nhỏ nhất của các
đa thức tối thiểu của các phần tử a,.
Ví dụ: Với m=4, t=2 thì mã BCH có chiều dài từ mã là
và có khoảng cách Hamming .
Cho a là phần tử có đa thức tối thiểu là đa thức căn bản có b ậc 4
sau
Chúng ta có ma trận kiểm tra của bộ mã như sau:
- Thay mỗi phần tử bằng vecto (m=4 thành phần) tương ứng ta được
Đa thức sinh g(x) là bội số của 2 đa thức tối thiểu tương ứng với
phần tử a và , ta có đa thức tối thiểu của là
Nên
=
2. Mã Reed – Solomon:
Mã Reed – Solomon thường được kí hiệu là RS(n,k)
-
Tương tự mã BCH nhị phân, điểm khác biệt giữa 2 loại mã này là các
-
thành phần trong đa thức sinh không phải chỉ là các bit nhị phân mà có
thể có dạng là 1 đa thức con. Chẳng hạn:
Một số ứng dụng:
•
Mã Reed – Solomon được sử dụng để sửa các lỗi trong nhiều hệ
thống và có thể kể ra một số như sau:
Các thiết bị lưu trữ (băng từ, đĩa CD, VCD…)
Thông tin di động hay không dây (Điện thoại di động, các đ ường
truyền viba…)
Truyền hình số DVB
Các modem tốc độ cao trong ADSL, VDSL….
…
nguon tai.lieu . vn
