Câu hỏi vui! Trên thực tế, chúng ta có thể nhận ra một cách hiệu quả không gian thông báo tối đa về kích thước $(q-1)^t({n\atop t})$.
Hãy bắt đầu với trường hợp $q=2$. Chúng tôi muốn tạo một chuỗi bit có độ dài $n$ và trọng lượng Hamming chính xác $t$. Có $C:=({n\atop t})$ các chuỗi như vậy và chúng tôi muốn ánh xạ một thông báo số nguyên từ khoảng $[0,C-1]$ đối với tập hợp này một cách khách quan. Nói một cách tổng hợp, tập hợp các chuỗi bit tương ứng với kết hợp (đặc biệt $t$-kết hợp của các số nguyên từ 0 đến $n-1$). Chúng ta có thể viết lại một cách khách quan chuỗi của mình dưới dạng một chuỗi giảm dần $t$ giá trị $n-1\ge c_t>c_{t-1}>\ldots>c_1\ge 0$ bằng cách viết ra các chỉ số về vị trí của 1s.
Bây giờ, một định lý tao nhã của toán học mà Knuth gán cho nhà toán học thế kỷ 19 Ernesto Pascal nói rằng mọi số $N$ có thể được đại diện trong hệ thống số tổ hợp
$$N=\left({c_t\atop t}\right)+\cdots+\left({c_1\atop 1}\right)$$
và thứ tự này bước qua các kết hợp là thứ tự từ điển (đối với mục đích của chúng tôi, thứ tự đầu tiên $({n\atop t})$ mục nhập danh sách trọng lượng $t$ chuỗi chiều dài $n$). Do đó, nếu chúng ta có một số nguyên $N\in [0,C-1]$ chúng ta có thể sử dụng thuật toán tham lam để khôi phục $N$cân nặng $t$ chuỗi nhị phân được cho bởi hệ thống số tổ hợp. Đây là một số mã giả:
Khởi tạo i:=n-1, j:=t, rest=N
trong khi tôi>=0
nếu Nhị thức(i,j) > số dư
đặt bit i của chuỗi thành 0
khác
đặt bit i của chuỗi thành 1
j--
phần còn lại -= Nhị thức (i,j)
tôi--
Bản đồ đảo ngược là đơn giản.
Ví dụ, với $n=10$, $t=3$ có 120 kết hợp có thể xảy ra, chúng ta hãy tìm kết hợp thứ 17 (đếm 0-up). Đầu tiên ta tìm số tứ diện nhỏ nhất không lớn hơn 17; đây là $({5\trên cùng 3})=10$; chúng tôi đánh dấu vị trí thứ 5 và còn lại 7. Bây giờ ta tìm số tam giác nhỏ nhất không lớn hơn 7; đây là $({4\trên cùng 2})=6$; chúng tôi đánh dấu vị trí thứ 4 và còn lại 1. Bây giờ ta tìm số nhỏ nhất không lớn hơn 1; cái này $({1\trên cùng 1})=1$; chúng tôi đánh dấu vị trí số 1 và không còn lại gì. Chuỗi của chúng tôi là 0000110010. Nếu chúng tôi nhận được chuỗi chúng tôi tính toán $({5\trên cùng 3})+({4\trên cùng 2})+({1\trên cùng 1})=10+6+1=17$.
Đối với các bảng chữ cái tổng quát hơn, chúng ta có thể sử dụng quy trình trên để tạo các vị trí lỗi và sau đó chọn từ $q-1$ giá trị lỗi có thể cho mỗi vị trí. cụ thể để $M=C(q-1)^t$ là kích thước của không gian tin nhắn của chúng tôi. Đưa ra một tin nhắn $m\in[0,M-1]$ chúng tôi để $N=[m/(q-1)^t]$ để có thể $N\in[0,C-1]$ và tạo danh sách các vị trí như trên. Sau đó chúng tôi để $B=m\mod{(q-1)^t}$ và viết $B$ như một $t$-chữ số trong cơ số $(q-1)$ (cho phép các số 0 đứng đầu) và gán các giá trị chữ số+1 cho từng vị trí. Một lần nữa bản đồ đảo ngược là đơn giản.
Ví dụ: giả sử chúng ta có một bảng chữ cái thập phân và xem xét các chuỗi có độ dài 10 với 3 lỗi. Có 120*729=87480 tin nhắn có thể có; chúng ta hãy tìm thứ 12707. Chúng ta tìm thấy $N=[12707/729]=17$ và do đó tạo chuỗi bit giống như trên. Chúng ta tìm thấy $B=12707\mod{729}=314$ đó là 378 trong cơ sở 9. Thông báo của chúng tôi chuyển thành chuỗi lỗi 0000480090. Một lần nữa, nếu chúng tôi nhận được chuỗi này, chúng tôi sẽ rút ra các chữ số khác không theo thứ tự và trừ đi một chữ số cho mỗi số để đưa ra số cơ số 9 là 378 sao cho $B=314$ tương tự như vậy chúng ta biết rằng $N=17$ từ các vị trí lỗi và có thể tính toán $m=729N+B=12707$.
Chương 7.2.1.3 "Tạo ra tất cả các kết hợp" trong "Nghệ thuật lập trình máy tính" của Donald Knuth là một tài khoản xuất sắc, toàn diện (mặc dù gây mất tập trung) về các thuật toán khác để tạo ra các kết hợp.
