1. KHOẢNG CÁCH HAMMING - CHẶN PLOTKINCHO N LÀ SỐ NGUYÊN DƯƠNG, KÝ HI...

2.1. KHOẢNG CÁCH HAMMING - CHẶN PLOTKIN

Cho n là số nguyên dương, ký hiệu

[0, 1]

= { x

x

. . .x

| x

∈ { 0, 1 } , i = 1, 2, . . . , n }

là tập tất cả các xâu nhị phân độ dài n.

Định nghĩa 2.1. Cho hai xâu nhị phân x = x

. . . x

và y = y

. . .y

. Khi đó khoảng cách giữa hai xâu x

và y được định nghĩa là

d(x, y) = số vị trí i mà x

6 = y

.

Khoảng cách này gọi là khoảng cách Hamming thỏa tất cả các điều kiện của một khoảng cách

• d(x, x) = 0, ∀ x ∈ [0, 1]

;

• d(x, y) > 0, ∀ x 6 = y ∈ [0, 1]

;

• d(x, y) = d(y, x), ∀ x, y ∈ [0, 1]

;

• d(x, z) ≤ d(x, y) + d(y, z), ∀ x, y, z ∈ [0, 1]

.

Định nghĩa 2.2. Cho d là số nguyên dương. Gọi C là tập hợp tất các các xâu nhị phân trong [0, 1]

sao

cho

d(x, y) ≥ d, ∀ x 6 = y ∈ C.

Định lý 2.3 (PLOTKIN). Cho n, d là các số nguyên dương. Đặt M = | C | . Khi đó