辛格爾頓界
在 編碼理論 中, 以 Singleton 命名的 Singleton 界 是一個關於分組碼容量的粗略估計。下面約定分組碼 的碼長為 , 容量為 , 碼的最小距離為 。
Singleton 界的描述
編輯長度為 的分組碼 的最小距離定義為:
其中 是 和 之間的漢明距離。表達式 表示長度為 ,極小距離為 的 元分組碼所能容納的碼字個數的的最大值。
Singleton 界斷言
證明
編輯首先,長度為 的 元碼字最多有 個,因為每個位置上的字母有 個獨立可選的值。
若 為任意一個最小距離為 的 元分組碼。顯然,所有的碼字是兩兩不同的。如果我們刪除掉這些碼字的前 個字符,則新的碼字仍然兩兩不同,因為 中原有碼字間的漢明距離至少為 。因此新碼的碼字個數與舊碼是相同的。
新碼的碼字具有長度
- ,
所以至多有
個不同碼字. 由於舊碼的碼字個數 與新碼相同,所以:
最大距離可分碼(MDS codes)
編輯能達到 Singleton 界的分組碼稱為MDS (最大距離可分) codes。 這種碼的例子包括只有一個碼字的碼,由 中全體向量構成的碼(最小距離為 1),包含一個奇偶校驗位的碼 (最小距離為 2) 以及它們的 對偶碼. 這些常被稱為 平凡 的 MDS 碼.
對於二元碼,所有 MDS 碼都是平凡的。[1]
擴展閱讀
編輯注釋
編輯參考文獻
編輯- R.C. Singleton. Maximum distance q-nary codes. IEEE Trans. Inf. Theory. 1964, 10: 116–118. doi:10.1109/TIT.1964.1053661.
Further reading
- J.H. van Lint. Introduction to Coding Theory. GTM 86 2nd. Springer-Verlag. 1992: 61. ISBN 3-540-54894-7.
- F.J. MacWilliams; N.J.A. Sloane. The Theory of Error-Correcting Codes. North-Holland. 1977: 33,37. ISBN 0-444-85193-3.
- L. R. Vermani: Elements of algebraic coding theory, Chapman & Hall, 1996.