Mã vòng cyclic
1. Định nghĩa
Định nghĩa
Mã vòng cyclic là một mã khối tuyến tính C(n,k) mà nếu dịch các bit của một từ
mã ta cũng được ít nhất 1 từ mã.
Ví dụ :
Ví dụ như từ mà số 3 chính là từ mã số 1 dịch phải 1 bit.
Đa thức mã
Nếu từ mã là :
w=a0a1a2…an−1
Thì đa thức mã tương ứng là :
w
(
x
)
=a0+a1x+a2x2+…+an−1xn−1
Tính chất :
Nếu
w
(
i
)
là từ mã có được khi dịch từ mã
w
i bit thì :
w
(
i
)
(
x
)
=
[
xi∗w
(
x
)
]
mod
(
xn+1
)
2. Đa thức sinh
Trong các đa thức mã xây dựng từ các từ mã, tồn tại 1 đa thức mà từ đa thức
này có thể nhân đa thức tạo ra các đa thức khác. Đây chính là đa thức sinh.
Đa thức có bậc nhỏ nhất (khác đa thức 0) chính là đa thức sinh.
Ví dụ :
Đa thức sinh ở đây chính là :
g
(
x
)
=1+x+x3
Chú ý : khi chuyển từ đa thức mã thành từ mã, trọng số bắt đầu từ trái qua phải
g0g1g2… gn
a. Tính chất 1 : đa thức sinh là duy nhất
" Không có đa thức nào có cùng bậc với đa thức sinh".
Như đã nói, đa thức (khác 0) có bậc nhỏ nhất chính là đa thức sinh. Không có
đa thức nào có cùng bậc với đa thúc sinh
Ví dụ :
Trong bảng trên, chỉ có duy nhất
là có bậc 3. Không có đa thức nào
khác có bậc 3
b. Tính chất 2 : hệ số tự do
"Hệ số tự do
g0
của đa thức sinh phải bằng 1".
"Hệ số của
gn−k
của đa thức sinh phải bằng 1". ???????
Ví dụ :
g
(
x
)
=1+x+x3
c. Tính chất 3 : sinh từ mã
"Từ đa thức sinh ta có thể nhân đa thức để tạo ra các đa thức khác".
Ta có thể thấy rõ qua bảng của mã cylic C(7,4) trên.
Các đa thức nó bậc tối đa là
n−1
.
d. Tính chất 4 : bậc của đa thức sinh
Bậc của đa thức sinh của bộ mã C(n,k) là :
r=n−k
=> Đa thức sinh có dạng :
g
(
x
)
=1+g1x+g2x2+…+xn−k
Ví dụ : vẫn theo bộ mã C(7,4) bên trên, đa thức sinh có bậc 7-4=3
g
(
x
)
=1+x+x3
e. Tính chất 5 : g(x) là thừa số của x^n + 1
Đa thức sinh g(x) là một thừa số của đa thức
xn+1
. (tức
xn+1
chia hết cho g(x))
xn+1=g
(
x
)
. h
(
x
)
f. Tính chất 6 : tổng hợp
Tính chất tổng hợp :
"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) là đa thức sinh
của mã cyclic C(n,k)"
3. Mã hóa
a. Sử dụng đa thức sinh
Mã hóa thường
Nhân trực tiếp đa thức sinh với đa thức mã
Chú ý : mã hóa kiểu này chỉ cho từ mã thường không cho từ mã hệ thống
Ví dụ :
// chắc cứ dùng cái này cho nhanh??? :)))
Mã hóa hệ thống
Từ mã hệ thống
Khác với từ mã thường, từ mã hệ thống giữ nguyên mã đầu vào, chỉ thêm các
bit kiểm tra vào phía trước.
Ví dụ : như ví dụ phía dưới đây, với g(x) = 1 + x + x^3
Từ mã vào : 1010 -> từ mã ra : 001|1010
Mã hóa
- Để mã hóa thường : ta chỉ đơn giản là nhân trực tiếp đa thức mã với đa
thức sinh.
- Để mã hóa hệ thống : ta làm như sau
Chuyển mã cần mã hóa về đa thức thông tin u(x)
B1 : Nhân u(x) với
xn−k
B2 : Chia lấy dư
b
(
x
)
=
[
u
(
x
)
. xn−k
]
%g
(
x
)
B3 : Ta được từ mã :
u
(
x
)
. xn−k+b
(
x
)
Ví dụ :
Chú ý : các phép '+' là phép cộng module 2 :
Với :
- 1 + 1 = 0
- 1 + 0 = 1
- 0 + 0 = 0
Tip : theo phép '+' thường nếu lẻ (-1,1,3,5..) thì là 1. Nếu chẵn (-2,0,2,4) thì là 0.
Ví dụ :