辛格爾頓界

維基百科,自由的百科全書
前往: 導覽搜尋

編碼理論 中, 以 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