基本理論とは何？わかりやすく解説 Weblio辞書

基本理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/12 03:57 UTC 版)

ここではリード・ソロモン符号の基本的な理論と実装方法について述べる。なお符号理論の基本概念として以下に登場する加算記号( ⊕ {\displaystyle \oplus } )は全て直和ではなく各ビットごとの排他的論理和を表す。リード・ソロモン符号では r ビットの連続した固まりを一つのシンボルとし、 N個のシンボルすなわち r × N ビットの並びを一つの符号語とする。このとき K 個のシンボルが実際に送る情報、残りの (N-K)個のシンボルが後述する符号化で生成される冗長シンボルである。ただし r , N, K は以下の条件を満たすとする。 2 r > N > K > 0 {\displaystyle 2^{r}>N>K>0} ここで (N-K)/2 を t とした場合、リード・ソロモン符号は t 個までのシンボルの誤りを訂正することができる。リードソロモンではまず r × N ビットの並びをシンボルを係数とする (N-1)次の多項式の形で表す。図のように各8ビット列が次のようなシンボルに変換されたとする。このときこのビット列はリード・ソロモン符号では A x 3 ⊕ B x 2 ⊕ C x ⊕ D {\displaystyle \left.Ax^{3}\oplus Bx^{2}\oplus Cx\oplus D\right.} という多項式の形で表される。シンボルへの変換は以下のように行う。まず連続する r ビットを一つのシンボルとするのでシンボルは全部で 2 r 種類存在することになる。そこで 2 r 個の要素で構成される拡大ガロア体を定義する。具体的にはまず r 次の原始多項式から適当な物を一つ選ぶ、例としてここでは r = 8 とし以下のものを使用する。 x 8 ⊕ x 4 ⊕ x 3 ⊕ x 2 ⊕ 1 = 0 {\displaystyle x^{8}\oplus x^{4}\oplus x^{3}\oplus x^{2}\oplus 1=0} このときこの方程式の根を α とおくと α 8 ⊕ α 4 ⊕ α 3 ⊕ α 2 ⊕ 1 = 0 {\displaystyle \alpha ^{8}\oplus \alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus 1=0} であるため、 α 8 = α 4 ⊕ α 3 ⊕ α 2 ⊕ 1 {\displaystyle \alpha ^{8}=\alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus 1} と表すことが出来る。そこでこの関係を用いて次のようにαのべき乗を定義して各ビット列に対応させる。 α 0 = 1 ↔ 00000001 {\displaystyle \alpha ^{0}=1\leftrightarrow 00000001} α 1 ↔ 00000010 {\displaystyle \alpha ^{1}\leftrightarrow 00000010} α 2 ↔ 00000100 {\displaystyle \alpha ^{2}\leftrightarrow 00000100} α 3 ↔ 00001000 {\displaystyle \alpha ^{3}\leftrightarrow 00001000} ・・・ α 7 ↔ 10000000 {\displaystyle \alpha ^{7}\leftrightarrow 10000000} α 8 = α 4 ⊕ α 3 ⊕ α 2 ⊕ 1 ↔ 00011101 {\displaystyle \alpha ^{8}=\alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus 1\leftrightarrow 00011101} α 9 = α 8 × α = α 5 ⊕ α 4 ⊕ α 3 ⊕ α 1 ↔ 00111010 {\displaystyle \alpha ^{9}=\alpha ^{8}\times \alpha =\alpha ^{5}\oplus \alpha ^{4}\oplus \alpha ^{3}\oplus \alpha ^{1}\leftrightarrow 00111010} α 10 = α 9 × α = α 6 ⊕ α 5 ⊕ α 4 ⊕ α 2 ↔ 01110100 {\displaystyle \alpha ^{10}=\alpha ^{9}\times \alpha =\alpha ^{6}\oplus \alpha ^{5}\oplus \alpha ^{4}\oplus \alpha ^{2}\leftrightarrow 01110100} ・・・ α 254 = α 7 ⊕ α 3 ⊕ α 2 ⊕ α 1 ↔ 10001110 {\displaystyle \alpha ^{254}=\alpha ^{7}\oplus \alpha ^{3}\oplus \alpha ^{2}\oplus \alpha ^{1}\leftrightarrow 10001110} これに 0 ↔ 00000000 {\displaystyle 0\leftrightarrow 00000000} を加えることで全部で 256 = 2 8の元が出揃い、各ビット列との対応がとれる。

※この「基本理論」の解説は、「リード・ソロモン符号」の解説の一部です。
「基本理論」を含む「リード・ソロモン符号」の記事については、「リード・ソロモン符号」の概要を参照ください。

基本理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/16 01:57 UTC 版)

「整関数」の記事における「基本理論」の解説

複素解析函数 f が z に関して正則とすれば、テイラー–マクローリンの公式により点 z の周りで整級数 f ( s ) = ∑ n = 0 ∞ a n ( s − z ) n {\displaystyle f(s)=\sum _{n=0}^{\infty }{a_{n}(s-z)^{n}}} に展開される。整級数論により、上の級数は z を中心とし、コーシー–アダマールの定理により 1 R = lim sup n → ∞ | a n | 1 / n {\displaystyle {\frac {1}{R}}=\limsup _{n\to \infty }|a_{n}|^{1/n}} で与えられる半径 R をもつ開円板上で絶対かつ一様に収束することが分かる。複素解析函数論の主結果は、収束半径が z と最も近くにある特異点との間の距離 R によって決まることである。複素解析函数が整であるとは、それが複素数平面の任意の点において正則であるときに言う。したがって、整函数は有限の距離にある特異点を持たない。ある点 y において正則な函数は y において無限回微分可能であることを思い出そう。 f が整函数ならば、任意の点において正則であるから、収束整級数 f ( z ) = ∑ n ≥ 0 a n z n {\textstyle f(z)=\sum _{n\geq 0}a_{n}z^{n}} に展開され、また無限遠点を除いて特異点を持たないから整級数の収束半径は無限大であり、すなわちこの級数は任意の z に対して収束する。したがって lim sup n → ∞ | a n | 1 / n = 0 {\textstyle \limsup _{n\to \infty }|a_{n}|^{1/n}=0} が成り立つ。またそれゆえ、整函数の任意の階数の導函数もまた整函数になる。コーシーの積分公式: f ( z ) = 1 2 π i ∫ γ f ( s ) s − z d s {\displaystyle f(z)={\frac {1}{2\pi i}}\int _{\gamma }{{\frac {f(s)}{s-z}}ds}} は、分数式 1/(s − z) を整級数に展開することにより、各テイラー係数を積分 a n = f ( n ) ( z ) n ! = 1 2 π i ∫ γ f ( s ) ( s − z ) n + 1 d s {\displaystyle a_{n}={\frac {f^{(n)}(z)}{n!}}={\frac {1}{2\pi i}}\int _{\gamma }{\frac {f(s)}{(s-z)^{n+1}}}ds} によって決定できる。ただし上記の両方の積分では、積分路 γ は z を囲まない閉路とする。さらに M(R) を z を中心とする半径 R の円板上での函数の最大絶対値とすれば、極めて重要なコーシーの不等式（フランス語版） | a n | ≤ M ( R ) R n {\displaystyle |a_{n}|\leq {\frac {M(R)}{R^{n}}}} が簡単な論法により得られる。整函数に関する重要な結果としてリウヴィルの定理がある: 定理 (Liouville) 整函数が有界ならば、定数函数である。この定理はコーシーの不等式を適用して証明できる。すなわち、R が何であっても M(R) が有界であることに注意して、R を無限大に飛ばせば所望の結果を得る。このリウヴィルの定理から、代数学の基本定理「次数 n の任意の多項式は、重複度を込めて n 個の根を持つ」の簡単な証明が得られる。次のピカールの小定理はリウヴィルの定理の強化版であると考えられる: 定理 (Picard) 定数でない任意の整函数は、複素数平面上において、高々一つの値を除いたすべての複素数の値をとる。詳しくは後述するが、ある意味で整函数論はピカールの小定理のまったく周辺を周っている。一つの領域—つまり、連結開集合—上定義された正則函数が整函数に解析的に延長できるための必要十分条件は、そのテイラー級数の収束半径がその領域上の任意の点において無限大となることである。（注：領域上のある1点に於いてテイラー級数の収束判型が無限大であれば整関数に延長できる。）整函数全体の成す集合は、写像の合成に関して閉じているから、複素数平面からそれ自身への連続函数全体の成す空間の複素部分多元環を成す。整函数は有界ならば定数であり、また無限遠点以外では特異点を持てないから、定数でない任意の整函数に対して無限遠点は特異点である。可能性としてその特異点は極または真性特異点であるが、前者の（無限遠点に極を持つ）場合、その整函数は多項式である。後者の（無限遠に真性特異点を持つ）場合、その函数は超越整函数と言う。孤立零点の原理函数 f は領域 U 上で定義された解析函数で、a において消えているとする。このとき、f は恒等的に零か、さもなくば a を中心とする円板 D が存在して、a と異なる任意の s ∈ D に対して f(s) ≠ 0 が成り立つ。これは解析接続の原理からの帰結である。開写像定理開集合 U 上で定数でない解析函数 f に対し、f(U) もまた開集合である。これは孤立零点の原理によっても示せる。最大値原理領域 D 上で定数でない解析函数 f に対し、開写像定理から以下が直ちに従う:f の絶対値は D に極大値を持たない（したがって、D が有界ならば |f| は D の境界上で最大値を持つ）; f が D 上で消えないならば、|f| は D に極大値を持たない; f の実部は D に極大値も極小値も持たない。特にシュヴァルツの補題が導ける。より一般に、任意の劣調和函数（例えば |f| や f が消えない場合の 1/|f| などはそう）は最大値の原理を満足する。また任意の調和函数（例えば Re(f) はそう）は最大値および最小値の原理を満足する。フラグメン–リンデレーフの原理（英語版）は最大絶対値の原理の非有界領域への一般化である。

※この「基本理論」の解説は、「整関数」の解説の一部です。
「基本理論」を含む「整関数」の記事については、「整関数」の概要を参照ください。

基本理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/09 04:48 UTC 版)

「シクロール仮説」の記事における「基本理論」の解説

リンチはバナールの提案を本格的なタンパク質構造の模型へと発展させた。基本的なシクロール模型はリンチの最初の論文（1936年）で説明されている。リンチは、ポリペプチドが環化して閉じた環を形成するかもしれないこと（環状ペプチドが存在するのでこれは真である）、これらの環がシクロール反応によって内部架橋を形成するかもしれない（これも真であるが、稀である）という可能性を記している。ペプチド結合のシクロール形がアミド形よりも安定であると仮定して、リンチは、特定の環状ペプチドが自然に最大数のシクロール結合を形成するだろう、と結論付けた。もし分子中の化学結合がおおよそ 1.5 オングストロームの同じ長さを取るならば、こういったシクロール分子は六方対称性を有する。これらの環は無限に拡大して、シクロール生地を形成できる（図3）。こういった生地は、長距離の準結晶性秩序を示す。タンパク質は何百もの残基を密に詰め込まなければならないため、リンチはこれがタンパク質においてありえそうだと考えた。こうういった分子および生地のもう1つの興味深い特徴は、それらのアミノ酸側鎖が1つの面からだけ軸方向に上向きになっており、反対側の面には側鎖がないことである。これは、タンパク質の配列に依存しない性質を説明するものではないかと、リンチは推測した。最初の論文において、リンチは、シクロール模型が単なる「作業仮説」に過ぎず、タンパク質のモデルとして有効である可能性があるが、それを確認する必要がある、と明白に述べている。この論文とその続報におけるリンチも目標はよく定義された検証可能な模型を提案すること、その仮定の結果を検討すること、実験的に検証可能な予測を行うこと、であった。これらの目標においては、リンチは成功した。しかしながら、数年のうちに、実験とさらなるモデリングが、シクロール仮説が球状タンパク質の模型として擁護できないことを示した。

※この「基本理論」の解説は、「シクロール仮説」の解説の一部です。
「基本理論」を含む「シクロール仮説」の記事については、「シクロール仮説」の概要を参照ください。

基本理論

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/12 01:33 UTC 版)

「キャリー付き乗算」の記事における「基本理論」の解説

MWC 列は b を法とする剰余からなる。b = 232 とするのが普通だが、これはコンピュータで扱う整数が通常そのようになっているからである。ただ、b = 232 − 1とすることもある。これは、232 − 1 を法とする演算は 232 を法とする演算を少し変更するだけで済み、さらに、b = 232 の MWC の理論にはいくつか厄介な問題があるが、b = 232 − 1 ではそれを回避できるからである。その最も一般的な形では、lag-r MWC 生成器は基数 b、乗数 a、そして r + 1 個の乱数種を必要とする。乱数種は r 個の b の剰余 x0, x1, x2 ,..., xr−1 と最初のキャリー cr−1 < a である。そして、lag-r MWC 列は x n = ( a x n − r + c n − 1 ) mod b , c n = ⌊ a x n − r + c n − 1 b ⌋ , n ≥ r {\displaystyle x_{n}=(ax_{n-r}+c_{n-1})\,{\bmod {\,}}b,\ c_{n}=\left\lfloor {\frac {ax_{n-r}+c_{n-1}}{b}}\right\rfloor ,\ n\geq r} で定義される xn, cn のペアの数列であり、MWC 生成器の出力は以下の x の列となる。 xr , xr+1 , xr+2, ... lag-r MWC 生成器の周期は abr − 1 を法とする数の乗法群における b の位数である。通例、a は b の位数を大きくできるよう、p = abr − 1 が素数になるように選ぶ。b = 232 は p = abr − 1 の原始根とはならないので、b = 232 を基数とした MWC 生成器の周期は、MWC の最大周期 p = abr − 2 になることはない。これが、b = 232 − 1 の方が有利になる点の1つである。 Couture と l'Ecuyer (1997) により、MWC 生成器には最上位ビットが少し偏っているという理論的な問題があると指摘された。ただし、この問題は相補的キャリー付き乗算により解決されている。「相補的 MWC を使えば、最上位ビットは均一に出ることが分かるだろう。つまり、全周期中で0と1とが同等の頻度で現れ、その傾向も MWC 生成器間に関連性はない。」彼らはビットの偏り具合についてそれ以上詳しくは語っていないようである。相補的 MWC 生成器は計算時間が若干増えるため、実装の要求によってどちらを使うか決めるといいだろう。