Giáo trình: Lý thuyết thông tin.
Ma trận đặc trưng của thanh ghi: T=

⎥
⎥
⎥
⎥
⎦
⎤
⎢
⎢
⎢
⎢
⎣
⎡
0101
1000
0100
0010
Chu kỳ của thanh ghi
Như đã trình bày ở trên về quá trình dịch chuyển lùi từng bước của thanh ghi:
Nếu ta gọi x
(0)
=
⎟
⎟
⎟
⎟
⎟
⎟
⎠

=T
2
.x
(0)
Giá trị của thanh ghi sau 3 xung đồng hồ là x
(3)
=T.x
(2)
=T
3
.x
(0)
----------------
Giá trị của thanh ghi sau n xung đồng hồ là x
(n)
=T.x
(n-1)
=T
n
.x
(0)
(bởi vì số trạng thái thông tin khác
nhau có thể có là 2
m
)

Vậy chu kỳ của thanh ghi là số xung nhịp đồng hồ để thanh ghi lặp lại trạng thái ban đầu. Nghĩa là
nếu x
(0)
≠0 và ∃ n>0 sao cho x

0
x
(i)
Ví dụ tìm chu kỳ của thanh ghi
Cho thanh ghi lui từng bước như hình sau:

+
F3 F
1
F
2
F
0
Từ thanh ghi ta có: m=4, a
0
=1, a
1
=0, a
2
=1, a
3
=0.
Ma trận đặc trưng của thanh ghi: T=

⎥
⎥
⎥

⎜
⎜
⎝
⎛
3
2
1
0
x
x
x
x
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
1
0
0
0

⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
1
0
1
0
(3)
=T.x
(2)
=

⎟
⎟
⎟
⎟
⎟
⎠
⎞

⎛
0
0
1
0
(5)
=T.x
(4)
=
⇒ x
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
0
0
0
1
(6)
=T.x

(0)
= 0 thì ta có chu kỳ n = 1. Chu kỳ n=6 Chu kỳ n=6 Chu kỳ n=3 Chu kỳ n=1
14
8
4
1
7
3
5
2
10
0
11 13
6
1512
9
Thanh ghi trên có 4 chu kỳ.
Bài tập
1.

Tìm các chu kỳ của thanh ghi lui từng bước như hình sau:

Sau khi hoàn tất bài học này bạn có thể:
Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu.
82
Giáo trình: Lý thuyết thông tin.
-
Biết cách xác định ma trận kiểm tra chẵn lẻ cho mã xoay vòng (hay còn gọi là mã
vòng),
-
Hiểu định nghĩa mã xoay vòng,
-
Vận dụng xây dựng bộ mã xoay vòng,
-
Vận dụng phương pháp sinh nhanh bộ mã xoay vòng để sinh bộ mã kiểm tra chẵn lẻ.
Ma trận kiểm tra chẵn lẻ mã xoay vòng
Định nghĩa:
ma trận kiểm tra chẵn lẻ được thiết kế từ thanh ghi lùi từng bước là ma trận có dạng
sau:
A=[x
(0)
| T x
(0)
|T
2
x
(0)
|…|T
n-1
x
(0)
] với n là chu kỳ của thanh ghi (n > m)

⎡
==
000101
001010
010100
101000
] x x x x x x[A
(5)(4)(3)(2)(1)(0)
Định nghĩa mã xoay vòng
Mã xoay vòng là mã kiểm tra chẵn lẻ được sinh ra từ ma trận kiểm tra chẵn lẻ ứng với chu kỳ n
của thanh ghi lùi từng bước có dạng như:
A=[x
(0)
| Tx
(0)
|T
2
x
(0)
|…|T
n-1
x
(0)
]

Ví dụ: xét lại ma trận kiểm tra chẵn lẻ ở trên
⎥
⎥
⎥
⎥

mã xoay vòng sinh từ thanh ghi lùi từng bước nêu trên
(Các bước sinh mã nhanh đề nghị các
bạn tự làm)
Phương pháp sinh nhanh bộ mã xoay vòng
Cách sinh nhanh k từ mã độc lập tuyến tính của bộ mã vòng từ a
0
,

a
1
,

a
2
, …, a
m-1
:
Bước 1:
sinh mã xoay vòng đầu tiên
Sinh mã xoay vòng đầu tiên có dạng w
1
=a
0
a
1
a
2
…a
m-1
1000…00

…a
m-1
1 (dịch từ w
k-1
sang phải 1 bit).

k-1 bit 0

Bước 3:
xác định các từ mã còn lại của bộ mã
Các từ mã còn lại gồm (2
k
– k từ mã) được xác định bằng cách cộng tổ hợp của 2, 3, …, k từ mã
từ k từ mã độc lập tuyến tính ở trên.
Ví dụ sinh nhanh bộ mã xoay vòng
Cho thanh ghi lui từng bước như hình sau:

+
F3 F
1
F
2
F
0
Từ thanh ghi, ta có: m=4, n=6, a
0
=1, a

1
+w
2
+ w
3
)
Bộ mã vòng vừa sinh là W={000000, 101010, 010101, 111111)

Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu.
84
Giáo trình: Lý thuyết thông tin.
Bài tập
1.

Cho thanh ghi lùi từng bước sau:

-

Tìm ma trận kiểm tra chẵn lẻ có số cột n > 4
+
F
0
F
1
F
2
-

Biên soạn: TS. L ê Quy ết Thắng, ThS. Phan Tấn Tài & Ks. Dương Văn Hiếu.
85