BCH符号(BCH code)とは、1 の原始 $n$ 乗根 $\beta$ の連続した冪 $\beta^b,\dots,\beta^{b+\delta-2}$ をすべて根にもつ語からなる巡回符号で、$\delta$ を設計距離という。BCH の限界により最小距離は $\delta$ 以上で、次元は $n-m(\delta-1)$ 以上($m$ は $q$ の $n$ を法とする位数)、二元で狭義なら $n-m\lceil(\delta-1)/2\rceil$ 以上である。原始的で狭義の BCH 符号は Reed–Solomon 符号の部分体部分符号であり、連続した根から作るシンドロームの行列で誤りの個数と位置を求め、$\lfloor(\delta-1)/2\rfloor$ 個までの誤りを訂正できる。
前提知識: 巡回符号, 有限体, Reed–Solomon符号
BCH 符号(BCH code)は、望む最小距離 $\delta$ を先に決めて、それを保証するように作る 巡回符号 である。$\beta$ を 1 の原始 $n$ 乗根として、$\beta^b,\beta^{b+1},\dots,\beta^{b+\delta-2}$ という連続した $\delta-1$ 個の冪を根にもつ語の全体をとる。最小距離が $\delta$ 以上になることは 巡回符号 の定理「BCH の限界」が保証する。名は発見者の Bose・Ray-Chaudhuri と Hocquenghem による(GRS25 第 5 章の脚注、p. 105、および文献の注、p. 112)。
この記事では、BCH 符号の次元の下からの評価(thm-bch-basic)、Reed–Solomon符号 との関係(prop-bch-rs)、連続した根を使って $\lfloor(\delta-1)/2\rfloor$ 個までの誤りを訂正する復号の方法(thm-bch-decode)を述べる。Reed–Solomon 符号は文字の集合が大きい体でないと長くできないが、BCH 符号は二元のような小さい体の上で長い符号を与える。その代わり、次元は一般に Singleton の限界より小さく(例えば $[15,7,5]_2$ では $7< 15-5+1$)、MDS 符号になるとは限らない(同じ長さの $[15,1,15]_2$ は反復符号で MDS 符号である)。
以下、$q$ は素数冪、$\mathbb F_q$ は位数 $q$ の 有限体、$n\ge2$ は $\gcd(n,q)=1$ を満たす整数とし、語を多項式 $c(x)=\sum_{i=0}^{n-1}c_ix^i$ と同一視するなど、記号は 巡回符号 の記事に従う。$m$ を $q$ の $n$ を法とする位数とし、$\mathbb F_q\subset\mathbb F_{q^m}$ とみなして、1 の原始 $n$ 乗根 $\beta\in\mathbb F_{q^m}$ を 1 つ固定する。$\mathbb Z/n\mathbb Z$ の円分剰余類($q$ 倍で閉じた最小の集合)も 巡回符号 の意味で使う。
整数 $b$ と $2\le\delta\le n$ について、$J:=\{b,b+1,\dots,b+\delta-2\}$($n$ を法として)とおき、
$$
\mathrm{BCH}_q(n,\delta,b):=\{c\in\mathbb F_q^n : c(\beta^j)=0\ \ (j\in J)\}
$$
を長さ $n$、設計距離 $\delta$ の BCH 符号 という。$b=1$ のとき 狭義の BCH 符号、$n=q^m-1$ のとき 原始的な BCH 符号という。
符号は $\beta$ のとり方に依存するが、別の原始 $n$ 乗根をとっても座標の並べ替えで移り合う符号になる。以下では $\beta$ を固定して考える。$J$ を含む $q$ 倍で閉じた最小の集合、すなわち $J$ の元を含む円分剰余類の和集合を $Z_J$ と書く。
$C:=\mathrm{BCH}_q(n,\delta,b)$ とする。
1:$c\in\mathbb F_q^n$ の係数は $\mathbb F_q$ にあるので、有限体 の命題「Frobenius写像の性質」($a\mapsto a^q$ はその合成なので環準同型)と系「有限体における $x^q=x$」(係数について $c_i^q=c_i$)により $c(\beta^{qj})=c(\beta^j)^q$ である。よって $c(\beta^j)=0$ なら $c(\beta^{qj})=0$ で、これを繰り返すと、$J$ の元で $0$ になる語は $Z_J$ のすべての元で $0$ になる。逆は $J\subset Z_J$ から明らかなので、1 つ目の等式が成り立つ。
$Z_J\ne\mathbb Z/n\mathbb Z$ なら、巡回符号 の定理「零点による判定」の 3 により $P:=\prod_{i\in Z_J}(x-\beta^i)$ は $\mathbb F_q[x]$ の多項式で、$P$ の生成する巡回符号 $C'$ の零点の集合は $Z_J$ である。同じ定理の 1 により $C'=\{c : c(\beta^i)=0\ (i\in Z_J)\}=C$ である。$C'$ は $P$ を含むので $\{0\}$ でない。$Z_J=\mathbb Z/n\mathbb Z$ なら、$c\in C$ は次数 $n-1$ 以下で相異なる $n$ 個の根 $\beta^0,\dots,\beta^{n-1}$ をもつので $c=0$ である。
2:$J\subset Z(C)$ なので、巡回符号 の定理「BCH の限界」による。
3:$C\ne\{0\}$ なら $\dim C=n-\deg P=n-\lvert Z_J\rvert$ である(巡回符号 の定理「生成多項式」)。$C=\{0\}$ でも両辺は $0$ である。$i$ を含む円分剰余類は $\{i,qi,\dots,q^{m-1}i\}$ に含まれる($q^mi\equiv i$)ので、元の個数は $m$ 以下である。$Z_J$ は $J$ の $\delta-1$ 個の元のそれぞれを含む円分剰余類の和集合なので、$\lvert Z_J\rvert\le m(\delta-1)$ である。
4:$J=\{1,\dots,\delta-1\}$ の偶数 $j=2j'$ について $1\le j'\le(\delta-1)/2$ なので $j'\in J$ で、$j$ は $j'$ と同じ円分剰余類に入る。偶数の元を奇数になるまで $2$ で割っていくと、$Z_J$ は $J$ の奇数の元を含む円分剰余類の和集合である。$J$ の奇数の元は $\lceil(\delta-1)/2\rceil$ 個なので、$\lvert Z_J\rvert\le m\lceil(\delta-1)/2\rceil$ である。$\square$
3 と 4 の評価は、円分剰余類がすべて $m$ 個の元をもち、互いに重ならないときに等号になる。小さい剰余類があれば次元は評価より大きい(下の ex-bch-15 の $\delta=7$)。逆に、別の $j\in Z_J$ が連続した列を延ばすこともあり、そのときは同じ符号がより大きな設計距離をもつ(下の表の $n=31$ の $\delta=9$ と $\delta=11$)。
原始的で狭義の BCH 符号は、大きい体の上の Reed–Solomon符号 のうち、成分がすべて小さい体に入る符号語を集めたもの(部分体部分符号)である。
$n=q^m-1$ とし、$\alpha:=\beta$ を $\mathbb F_{q^m}$ の原始元、$\mathbf a:=(1,\alpha,\dots,\alpha^{n-1})$ とする。$2\le\delta\le n$ について
$$
\mathrm{BCH}_q(n,\delta,1)=\mathrm{RS}_{q^m}(\mathbf a,\,n-\delta+1)\cap\mathbb F_q^n
$$
である。
Reed–Solomon符号 の定理「根の条件による記述」を $k=n-\delta+1$ として使うと、$\mathrm{RS}_{q^m}(\mathbf a,k)=\{c\in\mathbb F_{q^m}^n : c(\alpha^j)=0\ (j=1,\dots,\delta-1)\}$ である。両辺の $\mathbb F_q^n$ との共通部分をとると、右辺は定義の $\mathrm{BCH}_q(n,\delta,1)$ である。$\square$
この命題から、最小距離が $\delta$ 以上であることは、Reed–Solomon 符号が $[n,n-\delta+1,\delta]_{q^m}$ の MDS符号 であることからも分かる。部分集合をとっても $0$ でない語の重みは小さくならないからである。一方、次元は $\mathbb F_{q^m}$ 上の $n-\delta+1$ から大きく減り、thm-bch-basic の 3 の評価は「$\mathbb F_{q^m}$ 上の $\delta-1$ 本の検査式を $\mathbb F_q$ 上の $m(\delta-1)$ 本に開く」ことに当たる。この見方は GRS25 Exercise 5.11(p. 105)の定義で、$q=2$ の場合の thm-bch-basic の 3・4 がその小問 1・2 の内容である。
$q=2$、$\delta=3$ なら $Z_J$ は $1$ を含む円分剰余類 $\{1,2,4,\dots,2^{m-1}\}$ で、$C=\{c : c(\alpha)=0\}$ となる。$\mathbb F_{2^m}$ を $\mathbb F_2^m$ と同一視して $\alpha^0,\dots,\alpha^{n-1}$ を列に並べた行列を $H$ とすれば、$H$ の列は $\mathbb F_2^m$ の $0$ でない元のすべてなので、$C$ は長さ $2^m-1$ の二元 Hamming符号 である($m=3$ の場合は 巡回符号 の例「長さ $7$ の Hamming 符号は巡回符号」)。
$C=\mathrm{BCH}_q(n,\delta,b)\ne\{0\}$ とし、$t:=\lfloor(\delta-1)/2\rfloor\ge1$ とおく($\delta\ge3$)。最小距離は $2t+1$ 以上なので、受け取った語 $r$ から距離 $t$ 以内にある符号語は高々 1 つである。符号語 $c$ を送り、$r=c+e$ を受け取ったとし、誤り $e$ の重みを $\nu$ とする。$e$ の $0$ でない座標を $i_1,\dots,i_\nu$ として
$$
X_l:=\beta^{i_l}\ \ (\text{誤りの位置}),\qquad Y_l:=e_{i_l}\ne0\ \ (\text{誤りの値})
$$
とおく。$\beta$ の位数は $n$ なので $X_1,\dots,X_\nu$ は相異なる $0$ でない元である。$1\le j\le2t$ について $b+j-1\in J$ なので $c(\beta^{b+j-1})=0$ で、受け取った語だけから計算できる シンドローム
$$
S_j:=r(\beta^{b+j-1})=e(\beta^{b+j-1})=\sum_{l=1}^\nu Y_lX_l^{\,b+j-1}\qquad(j=1,\dots,2t)
$$
が誤りの情報を運ぶ。誤り位置多項式 を $\Lambda(z):=\prod_{l=1}^\nu(1-X_lz)=1+\sigma_1z+\dots+\sigma_\nu z^\nu$ と定め、$1\le\mu\le t$ について $\mu\times\mu$ 行列 $M_\mu:=(S_{i+j-1})_{1\le i,j\le\mu}$ を考える。
上の記号で $\nu\le t$ とする。
1:$\mu\le t$ とし、$V$ を $(i,l)$ 成分が $X_l^{\,i-1}$ の $\mu\times\nu$ 行列、$D$ を対角成分が $Y_lX_l^{\,b}$ の $\nu\times\nu$ 対角行列とする。$i+j-1\le2\mu-1\le2t$ なので
$$
(VDV^{\mathsf T})_{ij}=\sum_{l=1}^\nu X_l^{\,i-1}\,Y_lX_l^{\,b}\,X_l^{\,j-1}=\sum_{l=1}^\nu Y_lX_l^{\,b+i+j-2}=S_{i+j-1}
$$
で、$M_\mu=VDV^{\mathsf T}$ である。$\mu>\nu$ なら $M_\mu$ の階数は $V$ の列の数 $\nu$ 以下で $\mu$ より小さく、$M_\mu$ は特異である($\nu=0$ なら $M_\mu=0$)。$\mu=\nu\ge1$ なら、$V$ は相異なる $X_1,\dots,X_\nu$ を節点とする Vandermonde 行列なので Vandermondeの行列式 の命題「正則性の判定」により正則で、$D$ も $Y_l\ne0$、$X_l\ne0$ から正則である。よって $M_\nu$ は正則である。
2:$z^\nu\Lambda(1/z)=\prod_l(z-X_l)=z^\nu+\sigma_1z^{\nu-1}+\dots+\sigma_\nu$ は $z=X_l$ で $0$ になる。$\nu+1\le j\le2\nu$ について、これに $Y_lX_l^{\,b+j-1-\nu}$ を掛けて $l$ について足すと
$$
S_j+\sigma_1S_{j-1}+\dots+\sigma_\nu S_{j-\nu}=\sum_{l=1}^\nu Y_lX_l^{\,b+j-1-\nu}\bigl(X_l^{\,\nu}+\sigma_1X_l^{\,\nu-1}+\dots+\sigma_\nu\bigr)=0
$$
である($j\le2\nu\le2t$ なので $S_j$ はシンドロームの中にある)。$j=\nu+i$($i=1,\dots,\nu$)とすると、これは $\sum_{s=1}^\nu S_{i+s-1}\sigma_{\nu-s+1}=-S_{\nu+i}$、すなわち問題の方程式の第 $i$ 行である。1 により $M_\nu$ は正則なので、解はただ 1 つである。
3:$\Lambda$ の根は $X_l^{-1}=\beta^{-i_l}$($l=1,\dots,\nu$)であり、$\beta^{-i}$($0\le i\le n-1$)は相異なるので、$\Lambda(\beta^{-i})=0$ となる $i$ はちょうど $i_1,\dots,i_\nu$ である。
4:係数行列 $(X_l^{\,j-1})_{j,l}$ は 1 の $V$($\mu=\nu$)の形で正則なので、未知数 $X_l^{\,b}Y_l$ はただ 1 つに決まり、$X_l\ne0$ で割って $Y_l$ が決まる。等式は $S_j$ の定義そのものである。$\square$
$\Lambda(\beta^{-i})$ を $i=0,1,\dots,n-1$ について順に計算して根を探す手順は Chien 探索 と呼ばれる。二元の場合は $Y_l=1$ なので 4 は要らず、さらに $S_{2j}=S_j^{\,2}$($b=1$ のとき)なので独立なシンドロームは奇数番目だけである。2 の方程式は Gauss の消去法で解けるが、$\nu$ が大きい符号では方程式の形(係数行列の成分が $S_{i+j-1}$ だけで決まる)を使う速い解き方が実用される。$\nu>t$ のときはこの手順は送った符号語を返すとは限らない(下の反例の表の 4 行目)。
$q=2$、$n=15$、$b=1$、$\delta=5$ とし、$\beta$ を $x^4+x+1$ の根にとる($\beta^4=\beta+1$)。巡回符号 の例「BCH 符号の例」の 2 のとおり、生成多項式は $g=x^8+x^7+x^6+x^4+1$ で、$t=2$ である。情報 $1+x+x^3$ の符号語 $c=(1+x+x^3)g$ の係数を $c_0,c_1,\dots,c_{14}$ の順に並べると
$$
c=110111110011000
$$
で、第 $3$・第 $10$ 座標が化けて $r=110011110001000$ を受け取ったとする。$\beta$ の冪で表すと
$$
S_1=\beta^{12},\quad S_2=\beta^{9},\quad S_3=\beta^{7},\quad S_4=\beta^{3}
$$
である($S_1=\beta^3+\beta^{10}$ など)。$\det M_2=S_1S_3+S_2^{\,2}=\beta^{19}+\beta^{18}=\beta^4+\beta^3=\beta^7\ne0$ なので $\nu=2$ である。Cramer の公式で
$$
\sigma_2=\frac{S_3^{\,2}+S_2S_4}{\det M_2}=\frac{\beta^{14}+\beta^{12}}{\beta^7}=\frac{\beta^5}{\beta^7}=\beta^{13},\qquad \sigma_1=\frac{S_1S_4+S_2S_3}{\det M_2}=\frac{1+\beta}{\beta^7}=\beta^{12}
$$
(標数 $2$ なので符号は気にしなくてよい)。$\Lambda(z)=1+\beta^{12}z+\beta^{13}z^2$ の根を探すと $z=\beta^{12}=\beta^{-3}$ と $z=\beta^5=\beta^{-10}$ で、誤りの位置は $3$ と $10$ である。
誤りが第 $6$ 座標の 1 個だけなら $S_1=\beta^6$、$S_2=\beta^{12}$、$S_3=\beta^3$、$S_4=\beta^9$ で、$\det M_2=\beta^9+\beta^{24}=0$ となり $M_2$ は特異、$M_1=(\beta^6)$ は正則なので $\nu=1$ である。$\sigma_1=S_2/S_1=\beta^6$、$\Lambda(z)=1+\beta^6z$ の根は $\beta^{-6}$ で、位置 $6$ が求まる。
$q=2$、$n=15$、$m=4$、$b=1$ とし、$\beta$ を $x^4+x+1$ の根にとる。$15$ を法とする円分剰余類は $\{0\}$、$\{1,2,4,8\}$、$\{3,6,12,9\}$、$\{5,10\}$、$\{7,14,13,11\}$ である。
| 設計距離 $\delta$ | $Z_J$ に加わる剰余類 | パラメータ | 生成多項式 $g$ |
|---|---|---|---|
| $3$ | $\{1,2,4,8\}$ | $[15,11,3]$ | $x^4+x+1$ |
| $5$ | $\{3,6,12,9\}$ | $[15,7,5]$ | $x^8+x^7+x^6+x^4+1$ |
| $7$ | $\{5,10\}$ | $[15,5,7]$ | $x^{10}+x^8+x^5+x^4+x^2+x+1$ |
| $9$〜$15$ | $\{7,14,13,11\}$ | $[15,1,15]$ | $1+x+\dots+x^{14}$ |
$\delta=3,5,7$ では $g$ 自身が重み $\delta$ の符号語なので、最小距離はちょうど $\delta$ である。$\delta=7$ の次元 $5$ は thm-bch-basic の 4 の評価 $15-4\cdot3=3$ より大きい。剰余類 $\{5,10\}$ の元が $2$ 個しかないからである。$\delta\ge9$ では零点の集合が $0$ 以外のすべてになり、反復符号になる。
次の表は $q=2$、$n=31$、$m=5$、$b=1$($\beta$ は $x^5+x^2+1$ の根)の場合で、$31$ を法とする $0$ 以外の円分剰余類は元が $5$ 個ずつの $6$ 個である。最小距離の列は、$\delta=3$ では $g$ の重みから、それ以外は全符号語($\delta=5$ では重み $5$ の符号語の全数)を調べる有限計算で求めた値である。
| 設計距離 $\delta$ | $J$ の奇数の元の剰余類 | パラメータ |
|---|---|---|
| $3$ | $1$ | $[31,26,3]$ |
| $5$ | $1,3$ | $[31,21,5]$ |
| $7$ | $1,3,5$ | $[31,16,7]$ |
| $9$、$11$ | $1,3,5,7$ | $[31,11,11]$ |
| $13$、$15$ | $1,3,5,7,11$ | $[31,6,15]$ |
$\delta=9$ の符号は、$5$ の剰余類 $\{5,10,20,9,18\}$ が $9,10$ を含むので零点の集合が $1,\dots,10$ を連続して含み、$\delta=11$ の符号と同じになる。BCH の限界はその最小距離 $11$ をちょうど与える。$\delta=13$ と $15$ でも同様で、$11$ の剰余類が $13$ を、$7$ の剰余類が $14$ を含む。
$q=2$、$n=23$ とすると、$2^{11}=2048=89\cdot23+1$ で $2$ の位数は $m=11$ である。$1$ を含む円分剰余類は
$$
\{1,2,4,8,16,9,18,13,3,6,12\}
$$
で、$1,2,3,4$ を含み $5$ を含まない。よって $b=1$、$\delta=5$ の BCH 符号は零点の集合がこの $11$ 個の $[23,12]$ 符号で、BCH の限界が保証するのは最小距離 $5$ 以上である。しかし実際の最小距離は $7$ である。パラメータ $[23,12,7]_2$ は Golay符号 の記事の二元 Golay 符号と同じで、$2^{12}\bigl(1+23+\binom{23}2+\binom{23}3\bigr)=2^{12}\cdot2^{11}=2^{23}$ なので、半径 $3$ の球の詰め込みの限界の等号が成り立つ(完全符号)。$\mathbb F_{2^{11}}$ を $x^{11}+x^2+1$ で作り、その根 $\alpha$ について $\beta=\alpha^{89}$ とすると、生成多項式は
$$
g=x^{11}+x^9+x^7+x^6+x^5+x+1
$$
で、$x^{23}-1=(x+1)\,g\,g^\ast$($g^\ast=x^{11}+x^{10}+x^6+x^5+x^4+x^2+1$ は $g$ の係数を逆に並べたもの)である。$g$ の重みが $7$ なので最小距離は $7$ 以下で、$7$ 以上であることは $2^{12}$ 個の符号語を調べる有限計算で確かめた。
$q=3$、$n=8$ とすると $m=2$ で、$\mathbb F_9$ を $x^2+2x+2$($=x^2-x-1$)で作り、その根を $\beta$ とする。$3$ 倍による $8$ を法とする円分剰余類は $\{0\}$、$\{1,3\}$、$\{2,6\}$、$\{4\}$、$\{5,7\}$ である。$b=1$、$\delta=4$ なら $J=\{1,2,3\}$ で $Z_J=\{1,2,3,6\}$、生成多項式は
$$
g=x^4+2x^3+2x+2
$$
である。$g$ の重みは $4$ で、BCH の限界と合わせて $[8,4,4]_3$ 符号である。次元 $4$ は thm-bch-basic の 3 の評価 $8-2\cdot3=2$ より大きい。$1$ と $3$ が同じ剰余類に入るからである。
thm-bch-basic と thm-bch-decode の仮定を 1 つずつ外す。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| $\beta$ の位数がちょうど $n$(def-bch-code) | $q=2$、$n=15$、位数 $5$ の $\gamma\in\mathbb F_{16}$ を $\beta$ の代わりに使い、$J=\{1,2,3,4\}$ | 最小距離が $\delta=5$ 以上であること(thm-bch-basic の 2) |
| $q=2$(thm-bch-basic の 4) | $q=3$、$n=8$、$b=1$、$\delta=3$ | $\dim C\ge n-m\lceil(\delta-1)/2\rceil$ |
| $b=1$(thm-bch-basic の 4) | $q=2$、$n=15$、$b=0$、$\delta=3$ | $\dim C\ge n-m\lceil(\delta-1)/2\rceil$ |
| 誤りの重み $\nu\le t$(thm-bch-decode) | $q=2$、$n=7$、$b=1$、$\delta=3$、$c=0$、第 $0$・第 $1$ 座標の誤り | 復号の結果が送った符号語であること |
各行の反例は、外した条件のほかの仮定を満たす。
1 行目:$\gamma$ の位数は $5$ なので $\gamma^5=1$ で、語 $1+x^5$(重み $2$)は $\gamma^j$($j=1,2,3,4$)を代入するとすべて $1+1=0$ になる。$\gcd(15,2)=1$、$\delta=5\le n$ で、外したのは原始 $n$ 乗根であることだけである。証明では $X_l=\gamma^{i_l}$ が相異なることが成り立たない($\gamma^0=\gamma^5$)。
2 行目:$J=\{1,2\}$、$Z_J=\{1,3\}\cup\{2,6\}$ で $\dim C=4$ だが、右辺は $8-2\cdot1=6$ である。$3$ 倍では $2$ と $1$ が同じ剰余類に入らない。
3 行目:$J=\{0,1\}$、$Z_J=\{0\}\cup\{1,2,4,8\}$ で $\dim C=10$ だが、右辺は $15-4\cdot1=11$ である。$J$ の元 $0$ が別の剰余類をつくる。
4 行目:$t=1$ で、$\beta$ を $x^3+x+1$ の根にとると $C$ は長さ $7$ の Hamming 符号である。$r=1+x$ から $S_1=1+\beta=\beta^3$、$S_2=S_1^{\,2}$ で、$M_1=(S_1)$ は正則なので $\nu=1$ と判定され、$\sigma_1=S_2/S_1=\beta^3$、$\Lambda(z)=1+\beta^3z$ の根 $\beta^{-3}$ から位置 $3$ を反転する。結果は $1+x+x^3=g$ で、送った $0$ と異なる。
BCH 符号の最小距離は設計距離以上だが、ex-bch-golay のように真に大きいことがあり、設計距離だけからは決まらない。零点の集合の中の連続した番号の列を最大に延ばした長さ $+1$(上の $n=31$ の表で $\delta=9$ に対する $11$)は設計距離を改善するが、ex-bch-golay ではそれでも $5$ で、本当の最小距離 $7$ に届かない。
二元の原始的で狭義の BCH 符号は、$t$ 個の誤りを訂正でき($\delta=2t+1$)、検査の記号の個数 $n-k$ は thm-bch-basic の 4 により $mt=t\log_2(n+1)$ 以下である。一方、$t$ 個の誤りを訂正できる長さ $n$、次元 $k$ の二元符号では、符号語を中心とする半径 $t$ の球が交わらないので $2^k\binom nt\le2^n$ で、$n-k\ge\log_2\binom nt\ge t\log_2(n-t+1)-\log_2t!$ である。よって $t$ を固定して $n\to\infty$ とすると、BCH 符号の検査の記号の個数は可能な最小値と $t$ だけで決まる定数の差しかない(GRS25 Exercise 5.11 の小問 5・6、p. 105)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する