「符号」の版間の差分
削除された内容 追加された内容
編集の要約なし タグ: モバイル編集 モバイルウェブ編集 |
rvv |
||
1行目:
{{otheruses|符号理論の符号(code)|数学の符号(sign)|符号 (数学)|その他の符号|符号 (曖昧さ回避)}}
[[ファイル:International Morse Code.svg|right|thumb|290px|モールス符号]]
[[符号理論]]において、'''符号'''（ふごう）または'''コード'''（{{lang-en-short|code}}）とは、[[シンボル]]の集合''S'', ''X''があるとき、''S''に含まれるシンボルのあらゆる系列から、''X''に含まれるシンボルの系列への[[写像]]のことである。''S''を[[情報源アルファベット]]、''X''を[[符号アルファベット]]という。すなわち符号とは、[[情報]]の断片（例えば、[[文字]]、[[語]]、[[句]]、[[ジェスチャー]]など）を別の形態や表現へ（ある記号から別の記号へ）変換する規則であり、変換先は必ずしも同種のものとは限らない。
[[コミュニケーション]]や[[情報処理]]において'''符号化'''（[[エンコード]]）とは、[[情報源]]の情報を伝達のためのシンボル列に変換する処理である。'''復号'''（[[デコード]]）はその逆処理であり、符号化されたシンボル列を受信者が理解可能な情報に変換して戻してやることを指す。
符号化が行われるのは、通常の読み書きや会話などの言語によるコミュニケーションが不可能な場面でコミュニケーションを可能にするためである。例えば、[[手旗信号]]や[[腕木通信]]の符号も個々の文字や数字を表していることが多い。遠隔にいる人がその手旗や腕木を見て、本来の言葉などに戻して解釈することになる。
== 理論 ==
[[情報理論]]や[[計算機科学]]において符号とは、情報源[[アルファベット (計算機科学)|アルファベット]]から[[符号アルファベット]]へと一意に符号化する[[アルゴリズム]]を指す。一連のシンボル（文章）については情報源アルファベットから符号アルファベットへの変換を逐一行い、それらを連結することで符号化がなされる。
大雑把な例を示す。写像
:<math>C = \{\, a\mapsto 0, b\mapsto 01, c\mapsto 011\,\}</math>
は符号を表しており、情報源アルファベットは集合 <math>\{a,b,c\}</math> であり、符号アルファベットは集合 <math>\{0,1\}</math> である。この符号を使って ''0011001011'' という符号文字列が得られたとする。これを符号語に分割すると ''0 – 011 – 0 – 01 – 011'' となり、復号すれば ''acabc'' というシンボル列が得られる。
[[形式言語]]理論の用語を使うと、符号の概念は次のように定義される。SとTという2つの有限集合があり、Sを情報源[[アルファベット (計算機科学)|アルファベット]]、Tを[[符号アルファベット]]とする。'''符号''' <math>C:\, S \to T^*</math> は、Sの個々のシンボルがTの元を使ったワード（シンボルの並び）に対応する[[写像]]であり、<math>S^*</math> から <math>T^*</math> への[[準同型]]写像に拡大すれば、情報源アルファベットの並びを符号アルファベットの並びへと自然に写像できる。
=== 可変長符号 ===
{{main|可変長符号}}
ここでは、情報源のそれぞれの文字をなんらかの辞書に従って[[符号語]]に符号化し、それらを連結して符号化された文字列を形成する符号を扱う。可変長符号は、元の文書でそれぞれの文字が出現する頻度が異なる場合に特に便利である。詳しくは[[コンパクト符号]]と[[エントロピー符号]]を参照。
[[接頭符号]]は語頭属性 (prefix property) を満たす符号である。接頭符号ではそれぞれの符号語が決して他の符号語の接頭部にならない。[[ハフマン符号]]は接頭符号を作る最も一般的なアルゴリズムであり、そのため接頭符号をハフマン符号と呼ぶこともあるが、ハフマン符号のアルゴリズムを使わずに接頭符号を作ることもできる。接頭符号の他の例として[[国際電話番号の一覧|国際電話の国番号]]、[[ISBN]]のグループ番号と出版者番号、[[W-CDMA]]で使われている2次同期コード (SSC) などがある。
[[クラフトの不等式]]は、可変長符号が一意に復号可能であるための必要条件を与える。
=== ブロック符号 ===
{{Main|ブロック符号|線型符号}}
{{節スタブ}}
=== 誤り訂正符号 ===
{{Main|誤り検出訂正}}
データを転送あるいは保存する際に誤りが起きにくいようにする方法として符号を使うこともある。そのような符号を[[誤り検出訂正|誤り訂正符号]]と呼び、格納または転送されるデータに注意深く冗長性を導入する。例えば、[[ハミング符号]]、[[リード・ソロモン符号]]、[[リード・マラー符号]]、[[直交符号]]、[[BCH符号]]、[[ターボ符号]]、[[ゴレイ符号]]、[[ゴッパ符号]]、[[低密度パリティ検査符号]]などがある。誤り訂正符号は、「バースト誤り」または「ランダム誤り」を検出することに最適化されている。
== 例 ==
| |||