編碼理論 中, 以 Singleton 命名的 Singleton 界 是一個關於分組碼容量的粗略估計。下面約定分組碼 的碼長為 , 容量為 , 碼的最小距離為

Singleton 界的描述

編輯

長度為   的分組碼   的最小距離定義為:

 

其中     之間的漢明距離。表達式   表示長度為  ,極小距離為    元分組碼所能容納的碼字個數的的最大值。

Singleton 界斷言

 

證明

編輯

首先,長度為    元碼字最多有   個,因為每個位置上的字母有   個獨立可選的值。

  為任意一個最小距離為    元分組碼。顯然,所有的碼字是兩兩不同的。如果我們刪除掉這些碼字的前   個字符,則新的碼字仍然兩兩不同,因為   中原有碼字間的漢明距離至少為  。因此新碼的碼字個數與舊碼是相同的。

新碼的碼字具有長度

 

所以至多有

 

個不同碼字. 由於舊碼的碼字個數   與新碼相同,所以:

 

最大距離可分碼(MDS codes)

編輯

能達到 Singleton 界的分組碼稱為MDS (最大距離可分) codes。 這種碼的例子包括只有一個碼字的碼,由  中全體向量構成的碼(最小距離為 1),包含一個奇偶校驗位的碼 (最小距離為 2) 以及它們的 對偶碼. 這些常被稱為 平凡 的 MDS 碼.

對於二元碼,所有 MDS 碼都是平凡的。[1]

非平凡的 MDS 碼包括 里德-所羅門碼 和其擴展版本.[2]

擴展閱讀

編輯

註釋

編輯
  1. ^ see e.g. Vermani (1996), Proposition 9.2.
  2. ^ see e.g. MacWilliams and Sloane, Ch. 11.

參考文獻

編輯

Further reading