符号

提供: miniwiki
2018/8/19/ (日) 17:23時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索


符号理論において、符号(ふごう)またはコード: 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] への準同型写像に拡大すれば、情報源アルファベットの並びを符号アルファベットの並びへと自然に写像できる。

可変長符号

ここでは、情報源のそれぞれの文字をなんらかの辞書に従って符号語に符号化し、それらを連結して符号化された文字列を形成する符号を扱う。可変長符号は、元の文書でそれぞれの文字が出現する頻度が異なる場合に特に便利である。詳しくはコンパクト符号エントロピー符号を参照。

接頭符号は語頭属性 (prefix property) を満たす符号である。接頭符号ではそれぞれの符号語が決して他の符号語の接頭部にならない。ハフマン符号は接頭符号を作る最も一般的なアルゴリズムであり、そのため接頭符号をハフマン符号と呼ぶこともあるが、ハフマン符号のアルゴリズムを使わずに接頭符号を作ることもできる。接頭符号の他の例として国際電話の国番号ISBNのグループ番号と出版者番号、W-CDMAで使われている2次同期コード (SSC) などがある。

クラフトの不等式は、可変長符号が一意に復号可能であるための必要条件を与える。

ブロック符号


誤り訂正符号

データを転送あるいは保存する際に誤りが起きにくいようにする方法として符号を使うこともある。そのような符号を誤り訂正符号と呼び、格納または転送されるデータに注意深く冗長性を導入する。例えば、ハミング符号リード・ソロモン符号リード・マラー符号直交符号BCH符号ターボ符号ゴレイ符号ゴッパ符号低密度パリティ検査符号などがある。誤り訂正符号は、「バースト誤り」または「ランダム誤り」を検出することに最適化されている。

コミュニケーションにおける簡略化のための符号

電信符号では単語をもっと短い語に置き換え、同じ情報を少ない文字数で素早く送るようにしている。

符号は簡略化のために使われることがある。電報が高速な長距離通信の最新手段だったころ、フレーズ全体を一つの単語(5文字)で符号化するという符号体系ができ、通信士はその符号語に精通するようになった。例えば、BYOXO は "Are you trying to weasel out of our deal?"(あなたは我々との取引から責任逃れしようとしているのか?)、LIOUY は "Why do you not answer my question?"(何故私の質問に答えないのか?)、BMULD は "You're a skunk!"(くそったれ!)、AYYLU は "Not clearly coded, repeat more clearly."(不明瞭、もっとはっきり繰り返せ)などがある。符号語は、長さ発音の容易さなど様々な理由から選定された。それら符号語の意味は商取引、軍事、外交、諜報などのニーズに合わせて設定されている。こういった符号語と意味の対応を記したコードブックとその出版業が登場し、中でも第一次世界大戦と第二次世界大戦の間にハーバート・オズボーン・ヤードリーが創設したブラック・チェンバーもコードブックを出版していた。このような符号は主に電信コストを抑えるために作られた。データ圧縮を目的としたデータ符号化はコンピュータより先行していたとも言える。そもそもモールス符号も、よく使われる文字を短い表現にしている。ハフマン符号などの技法は今でもデータの圧縮のためのアルゴリズムとしてコンピュータ上で使われている。

文字コード

文字を符号化したデータ通信符号として最もよく知られているものとしてASCIIがある。ある程度互換性を保ったいくつかのバージョンがあり、コンピュータ端末プリンター、他の通信機器などで広く使われている。128種のキャラクタを7ビットの二進数で表しており、1と0が7個並んだものである。例えば小文字の "a" は 1100001、大文字の "A" は 1000001 などとなっている。文字コードは他にも様々なものがあり、1バイトでそれぞれの文字を表すもの、整数符号点に文字を割り当てるもの(Unicode)、バイト列で文字を表すもの(UTF-8)などがある。

遺伝コード

生物は、生体の機能とその発達を制御する遺伝形質を持っている。それがDNAであり、その中に遺伝子と呼ばれるユニットが含まれる。遺伝子はコード(コドン)を通してタンパク質を作ることができ、そのコードは4種類のヌクレオチドが3つ並んだものであって、その並びが20種類のアミノ酸のいずれかに翻訳される。

ゲーデル符号

数学において、ゲーデル符号を基礎としてゲーデル不完全性定理の証明がなされた。その考え方の基本は、(ゲーデル数を使って)数学的記述を自然数に写像するというものだった。

暗号

暗号史において、コードブックを使った符号(符牒、暗号)は通信の秘密を守る手段として広く使われていたが、今では複雑なアルゴリズムを用いる暗号が使われている。

暗号は元の平文がわからないようにすることを意図しており、軍事・外交・諜報活動のための真剣なものから、ゲームなどの瑣末なものまで様々な技法が存在する。花、トランプ、衣服、扇、帽子、音楽、鳥など、様々なものに符号化することもあり、送り手と受け手の間で事前に意味について合意しておくことが必要である。

その他の例

を符号として用いる例がある。例えば信号機抵抗器などの受動素子カラーコード(抵抗値などを表す)などがある。また、自治体などによってはゴミの分別のために色分けしたゴミ入れを使う場合もある。音を符号として用いる例として、軍隊で使っていた信号ラッパ(ビューグル)がある。感覚器に障害のある人のためのコミュニケーションシステムとして手話点字があり、動きや触覚を符号として用いている。

楽譜音楽を符号化したものと言える。チェス囲碁将棋などは棋譜と呼ばれる符号体系で対局の記録をとる。

符号化のその他の例として次のものがある。

  • 認識における符号化 - 入ってくる刺激を解釈する基本的知覚プロセス。複雑な多段プロセスで知覚入力(光、音など)を意味のある体験へと変換していく。
  • コンテントフォーマット - 特定の種類のデータ情報に変換するための個別的な符号化フォーマットである。
  • 電子符号化 - 信号を伝送電子媒体に最適化した符号に変換することで、一般にコーデックで行う。
  • Neural encoding - 神経細胞での情報の表現方法
  • (人間などの)記憶の符号化 - 感覚を記憶に変換するプロセス

復号のその他の例として次のものがある。

符号と頭字語

頭字語や略称もコードの一種と見なすことができ、その意味ではあらゆる言語も記述体系も人間の思考を符号化するものと見ることもできる。

国際空港運送協会の空港コードは空港を識別する3文字のコードであり、荷物のタグなどで使われている。

場合によっては、元の語句が忘れ去られたり符号語が考案されたころと意味が変わってしまい、符号語が独自の存在(と意味)を持つに至ることもある。例えばアメリカなどの報道関係では "30" が「原稿の終り」を意味し、転じて「終り」の意味で報道以外でも使われることがある。

関連項目