1. Bảng mã tách được

Kiểm tra xem bảng mã W={a, c, ad, abb, bad, deb, bbcde} có phải là bảng mã tách được hay không?

Bước khởi tạo: S0={a, c, ad, abb, bad, deb, bbcde}
Bước 1: Khởi tạo S1={}

  • Vì a là tiền tố của ad nên đưa phần hậu tố “d” vào S1 => S1={d}.
  • Vì a là tiền tố của abb nên đưa phần hậu tố “bb” vào S1 => S1={d, bb}.
  • Kiểm tra điều kiện dừng: không thỏa -> qua bước 2.

Bước 2: Khởi tạo S2={}. Tính S2 từ S0 và S1. 

  • Vì d ∈ S1 là tiền tố của deb ∈ S0 nên đưa phần hậu tố “eb” vào S2 => S2={eb} 
  • Vì bb∈ S1 là tiền tố của bbcde ∈ S0 nên đưa phần hậu tố “cde” vào S2 => S2={eb, cde} 
  • Kiểm tra điều kiện dừng: không thỏa -> qua bước 3.

Bước 3: Khởi tạo S3={}. Tính S3 từ S0 và S2.

  • Vì c∈ S0 là tiền tố của cde ∈ S2 nên đưa phần hậu tố “de” vào S3 => S3={de} 
  • Kiểm tra điều kiện dừng: không thỏa -> qua bước 4.

Bước 4: Tính S4 từ S0 và S3. Tính S4 từ S0 và S3.

  • Khởi tạo S4={}.
  • Vì de∈ S3 là tiền tố của deb ∈ S0 nên đưa phần hậu tố “b” vào S4 => S4={b} 
  • Kiểm tra điều kiện dừng: không thỏa -> qua bước 5.

Bước 5: Tính S5 từ S0 và S4. Tính S5 từ S0 và S4.

  • Khởi tạo S5={}.
  • Vì b∈ S4 là tiền tố của bad ∈ S0 nên đưa phần hậu tố “ad” vào S5 => S5={ad}
  • Vì b∈ S4 là tiền tố của bbcde ∈ S0 nên đưa “bcde” vào S5 => S5={ad, bcde}
  • Kiểm tra điều kiện dừng: Vì S5 có chứa từ mã ad nên dừng lại và kết luận đây là bảng mã không tách được

2. Phân phối – Lượng tin – Entropy

– Chuyển sang bảng phân phối X\Y

Lượng ngẫu nhiên của triệu chứng: H(triêu chứng)

– Lượng ngẫu nhiên của bệnh: (hàng xác suất x cột phân phối)

    • P(Y=1) = PA.1A + PB.1B + PC.1C = 0,5 x 0,6 + 0,3 x 0,2 + 0,2 x 0 = 0,39
    • P(Y=2)
    • P(Y=3)
    • P(Y=4)

==> P (Y) = (p1, p2, p3, p4)

==> H (Y) = entropy P (Y)

– Lượng ngẫu nhiên bệnh khi biết triệu chứng: 

    • H (Y/X=1) = entropy X1
    • H (Y/X=2) = entropy X2
    • H (Y/X=3) = entropy X3

==> H(Y/X) = H (Y/X=1).P1 + H (Y/X=3).P2 + H (Y/X=3).P3 (tổng mỗi cái nhân với xác suất)

Lượng chuẩn đoán bệnh: I (Y/X) = H(Y) – H(Y/X)

Phần trăm: I(Y/X).100

3. Ma trận kiểm tra chẵn lẽ – Xây dựng bộ từ mã

Xây dựng bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: 

– Ta có: 

  • n=6
  • m=3
  • Số bit thông tin k = n – m = 3
  • Số từ mã s=2k =8 từ mã.

– Xây dựng bộ từ mã

    • w1 = r1 r2 r3 1 0 0
    • w2= r1 r2 r3 0 1 0
    • w3 = r1 r2 r3 0 0 1
  • Tìm w1 : {giải hệ phương trình —> r1, r2, r3
  • Tìm w2 : {giải hệ phương trình —> r1, r2, r3
  • Tìm w3 : {giải hệ phương trình —> r1, r2, r3
    • w0 = 000000
    • w1 = – – – – – –
    • w2 = – – – – – –
    • w3 = – – – – – –
    • w4 = w1 + w2
    • w5 = w1 + w3
    • w6 = w2 + w3
    • w7 = w1 + w2 + w3

==> W = {00000, …}

4. Xây dựng bộ sửa lỗi  bit – Cho ví dụ

– Bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 1) 

– Số 1 hàng chéo, chuyển cột thành hàng

– Quá trình sửa lỗi

  • – Giả sử nhận v=001101, tính C = A.v = 1000
  • – Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C, ta có z0 = 100000
  • – Giải mã w = v + z0 = 001101 + 100000 = 101101 = w2

5. Thanh ghi lùi từng bước

– Ta có: m=4, a0=1, a1=0, a2=1, a3=0. (phải qua trái)

Ma trận đặc trưng của thanh ghi:

(3×3 cố định 1 chéo, 000 cột đầu, 4 số theo thanh ghi)

Bộ mã xoay vòng

– Khởi tạo: (lấy côt đầu tiên của T)

– Tìm chu kì: (đẩy 1 bít lên và cộng bít lại dựa trên thanh ghi, cái nào 1 thì cộng lại)

(Chừng nào = khởi tạo thì dừng và tính số nhị phân tương ứng –> vẽ hình)

Tương tự: (Khi một số bị thiếu thì khởi tạo lại số đó theo mã nhị phân)

+ Khi chọn x(0) = 3 thi ta cũng có chu kỳ n = 6.
+ Khi chọn x(0) = 6 thì ta có chu kỳ n = 3.
+ Khi chọn x(0) = 0 thì ta có chu kỳ n = 1.

Thanh ghi trên có 4 chu kỳ.  

Ma trận kiểm tra chẵn lẻ:

Tập hợp các x0, x1… của chu kì lớn nhất lại thành ma trận.

Ví dụ: