基本情報技術者単語帳 - 基礎理論

一般に、基数が正の整数nであるような記数法を「n進数」あるいは「n進法」という。ある桁の一つ上の桁はn倍の数を表し、一つ下の桁はn分の一の数を表す。十進数では一の位の隣が十の位で、以降順番に百の位、千の位…というように桁上りしていく。小数点以下は十分の一の位、百分の一の位、千分の一の位…といった具合である。

コンピュータとn進法

コンピュータでは情報を二つの状態(スイッチのオン・オフ、電圧の高低、0と1、真と偽など)の組み合わせに置き換えて扱う関係上、二や二の冪乗(四、八、十六…)が区切りの良い数となり、数値を扱う際に内部的には十進数ではなく二進数や十六進数がよく用いられる。

二進数では桁が上がる毎に重みが二倍になり、一の位、二の位、四の位、八の位…という具合に桁上りする。十六進数では十六倍で、一の位、十六の位、二百五十六の位、四千九十六の位…という形になる。

二進数の表記は「10010110」のようにアラビア数字の「0」と「1」のみを用いる。十六進数ではアラビア数字に該当する数字のない十から十五をアルファベットの「A」から「F」に対応付けて代用し、「F3E4D5」のように書き表す記法が普及している。

基数の表記

日常生活では基数の指定がなければ十進数を表すが、異なる基数の数が混在する議論では値のみを書き表しただけでは何進法の数のことか分からないため、「(10010110)₂」「(F3E4D5)₁₆」のように下付き文字で基数を十進表記で付記する記法が用いられることがある。

プログラミング言語などでも十進数以外の数値リテラルをプログラムコードなどに直接書くことができるよう、表記の仕方が定められていることがある。例えば、C言語やその記法を受け継ぐ多くの言語は先頭に「0x」を付けると十六進数を表す。C++言語(C++14)のように「0b」でニ進数リテラルを表す言語もある。

位取り記数法における基数(radix)は各桁の重みを表しており、10進数であれば各桁の重みが右隣の10倍、左隣の1/10倍となり、2進数ならそれぞれ2倍、1/2倍となる。

基数変換ではこの各桁の重みを利用して、ある基数による数の表記を別の基数で表していく。例えば、2進数の「1101」を10進数に変換する場合、1×2<³ + 1×2<² + 0×2<¹ + 1×2<⁰ となり、結果は「13」となる。

また、2進数と16進数の場合、16進数の「0」は2進数の「0000」、「F」は「1111」というように2進数の4桁が16進数の1桁に相当するため、2進数を4桁ごとに区切って対応する16進数に、あるいはその逆に置き換えることで容易に相互の変換を行うことができる。

基数変換は数の表記の仕方を変えるだけであるため、原則として変換の前後で数の大きさそのものに変化はない。ただし、小数を扱う場合はある基数で有限小数であるものが別の基数に表すと循環小数になってしまう場合があり、有限桁で正確に表すことはできなくなってしまう。

普段我々が日常的な数字の読み書きや算術に用いる位取り記数法は「10進数」(十進数)で、一つの桁の表現に「0」から「9」の10種類の数字を使い、各桁の左の桁が10倍、右の桁は1/10を表している。

一方、2進数は一つの桁の表現が「0」と「1」の二通りしか無い記数法で、桁が一つ左へ移動する毎に値の重みが2倍に、右へ移動するごとに1/2倍になる。整数の右端の桁は1(2⁰)の位、その左は2(2¹)の位、その左は4(2²)の位、その左は8(2³)の位…といった具合に各桁の重みが決まる。

例えば、2進数の「1101」は左端から順に「8の位」が1、「4の位」が1、「2の位」が0、「1の位」が1であるため、10進数では 1×8 + 1×4 + 0×2 + 1×1 の「13」となる。逆に、10進数の「21」は、2のべき乗の足し算で表すと 16 + 4 + 1、すなわち 2⁴×1 + 2³×0 + 2²×1 + 2¹×0 + 2⁰×1 と表せるため、2進数では「10101」となる。

2進数とビット・バイト

2進数は二つの状態の組み合わせですべての数を表現することができるため、これをスイッチのオン・オフや電圧の高低、磁石のN極とS極、電荷の有無など、対となる物理的な状態に対応させることにより、機械による情報の記憶や伝達、演算を容易に取り扱うことができるようになる。

現代の電子式のコンピュータは原則としてすべての情報を2進数のデータに置き換えて処理を行い、2進数の1桁に相当するデータ量の最小単位を「ビット」(bit)という。実用上はある程度まとまった桁数のビット列を対象にデータの保存や操作を行うため、8ビットに相当する「バイト」(byte)という単位が用いられることが多い。1バイトは8桁の2進数に相当するため、2⁸＝256種類の状態を表現できる。

普段我々が日常的な数字の読み書きや算術に用いる位取り記数法は10進数(十進数/10進法)で、一つの桁の表現に「0」から「9」の10種類の数字を使い、各桁の左の桁が10倍、右の桁は10分の1を表している。

一方、桁が一つ左へ移動する毎に値の重みが8倍に、右へ移動するごとに1/8倍になる。すなわち、整数の右端の桁は1(8⁰)の位、その左は8(8¹)の位、その左は64(8²)の位、その左は512(8³)の位…といった具合に各桁の重みが決まる。

例えば、8進数の「10」は10進数(十進数)における「8」を表し、「755」は、10進数では 7×64 + 5×8 + 5×1 で「493」となる。小数点以下も同様で、小数点の右隣から順に、8分の1の位、64分の1の位、512分の1の位…というように続く。

コンピュータでは数値やデータを取り扱う際に2のべき乗ごとに区切るのが都合が良いため、記数法でも2のべき乗を基数とする表現がよく用いられる。8進数もその一つだが、実用上は2進数と16進数が主に使われるため、8進数が用いられることはあまりない。

プログラミング言語の中にはコード中に数値リテラルとして8進数を記載する記法を用意しているものもある。 例えば、PythonやJavaScriptでは先頭に「0o」(ゼロオー)をつけて「0o777」のように、C言語やC++言語、Java、古いJavaScript規格では先頭に「0」(ゼロ)をつけて「0777」のように書けば8進数と解釈される。

10進数では桁が一つ左へ移動する毎に値の重みが十倍に、右へ移動するごとに十分の一になる。すなわち、整数の右端の桁は一(10⁰)の位、その左は十(10¹)の位、その左は百(10²)の位、その左は千(10³)の位、といった具合に各桁の重みが決まる。

コンピュータでは二つの状態の組み合わせで数値を表現する2進数の方が都合が良いため、人間などが10進数で入力した値は内部でまず2進数による表現に変換されてから記録、伝送、計算などを行うようになっている。また、処理結果を人間などに提示する場合も、内部の2進数による表現から10進数の表記に変換して出力される。2進表現を「バイナリ」(binary)、十進表現を「デシマル」(decimal)と呼ぶことがある。

「10進」と「十進」

どのような基数の表記でも、右から2桁目が1で右端が0の値はすべて「10」となり、それらはすべての異なる値である(2進数の「10」は2、8進数の「10」は8、16進数の「10」は16である)ため、基数が十であることを示すために「10進数」「10進法」とするのは紛らわしく不適切であるとする考え方もあり、そのような場合は「十」 (同様に英語圏では “ten” あるいは “decimal” )という表記が好まれる。

普段我々が日常的な数字の読み書きや算術に用いる位取り記数法は10進数(十進数/10進法)で、一つの桁の表現に「0」から「9」の10種類の数字を使い、各桁の左の桁が10倍、右の桁は10分の1を表している。

一方、16進数では1の位、16の位、256の位…というように桁の重みが16倍ずつ変化する。16進数における「10」は10進数における「16」を意味する。小数点以下も同様で、小数点の右隣から順に、16分の1の位、256分の1の位、4096分の1の位…というように続く。

コンピュータはすべてのデータを2進数で表しており、これを8桁(8ビット)ずつまとめた「バイト」という単位でデータを取り扱う。16進数は一桁で2進数の4桁分(4ビット)の値を書き記すことができるため、1バイトのデータを「00」から「FF」までの2桁の16進数として表記する慣習がある。

表記法

10進数の表記には「0」から「9」まで10種類の数字が必要なように、16進数では一桁を16種類の数字で表す必要がある。我々が日常的に使う数字は10種類しかないため、10から15までの数を一桁で表現するために「A」から「F」までの6つのアルファベットで代用することが多い。

その場合、「0」から「9」までは10進数の値と同じで、10進数の10を「A」、11を「B」、12を「C」、13を「D」、14を「E」、15を「F」でそれぞれ表す。例えば、「A0」は10進数の「160」(16×10)、「FF」は「255」(16×15＋15)を表す。言語や処理系によるが、大文字と小文字は区別しない(どちらでもよい)ことが多い。

なお、複数の位取り表記法が混在する文書などの場合、記された数値がそれぞれ何進法なのかを明示するため「(9ABC)₁₆」「(1234)₁₀」のように右下に小さく10進表記で基数を記す場合がある。

各言語における表記

プログラミング言語やマークアップ言語などの数値リテラルでは、日常的な文書などと同じように単に数字を並べた表記は10進数とみなす場合が多く、16進数を記述する場合は先頭に特定の接頭辞を付けるなど特別な表記法を用いる。

多くの言語ではC言語などにならって「0xDEAD」のように先頭に「0x」を付記する表記法を採用しており、文字列中のコード参照では「￥x0D￥x0A」のように「￥x」(日本語圏以外では￥はバックスラッシュ)を用いる。

言語によっては「#x」(Schemeなど)「&h」(BASICなど)などを用いたり、末尾に「h」を付ける(一部のアセンブリ言語など)場合もある。HTMLやXMLなどにおける数値文字参照では「&#x266A;」のように「&#x」と「;」で挟む。

我々が普段数を書き表すのに「0」から「9」までの十種類の数字を用いる「十進数」(10進数)を使っているが、数字の種類は10個である必要はなく、(数字を用意できれば)何進数で表すこともできる。任意のn個の数字で書き表す表記法全体を総称してn進数と呼ぶ。

十進数では、数字を並べた列の中での位置(桁)が重みを表しており、整数の右端から一の位、十の位、百の位…というように一桁ごとに十倍あるいは十分の一になっていく。n進数も同様で、右端から一の位、nの位、n²の位、n³の位…という重みになっている。小数点以下も同様である。

コンピュータでは電気回路のオン・オフにすべての情報を対応付けて処理するため、数も「0」と「1」の二つの数字のみを用いた「二進数」(2進数)を用いる。ニ進数のデータは人間には読み取りにくいため、4桁ごとに一つの数字に置き換えた「十六進数」(16進数)もよく用いられる。十以上の数はアルファベットで表し、十は「A」、十五は「F」となる。

コンピュータ上で長い桁の数値を短いコードで表記したい場合には、アルファベットのAからZまでを十から三十五に対応付けた「三十六進数」(36進数)や、小文字のa～z、大文字のA～Zを別の数字に対応付ける「六十二進数」(62進数)が用いられることもある。

例えば、10進数の65という数に足し合わせるとちょうど一つ桁上りする自然数は、足すと100になる35であり、(10進数における)「65に対する10の補数」という。また、足しても桁が増えない最大の数は、足すと99になる34であり、(10進数における)「65に対する9の補数」という。

1の補数 (one's complement)

ある自然数を2進数(2進法)で表現したときに、足し合わせるとすべての桁が1になる最大の数のことを「1の補数」という。足してもギリギリ桁が増えない最も大きな数である。

たとえば、「10010110」に対する1の補数は「1101001」であり、両者を足し合わせると「11111111」(8桁すべてが1)となる。コンピュータで取り扱う際には、各桁の0を1に、1を0にするビット反転によって求めることができ、それに1を加えたものは2の補数となる。

2の補数 (two's complement)

ある自然数を2進数(2進法)で表現した時に、足し合わせると桁が増える最小の数を「2の補数」という。足すと一桁増えて先頭の桁が1、残りの桁が0となる数である。

例えば、「10010110」に対する2の補数は「1101010」であり、両者を足し合わせると「100000000」(桁が一つ増えて既存の8桁がすべて0)となる。コンピュータで取り扱う際には元の数のビット反転によって求められる1の補数に1を足せば2の補数となる。コンピュータ上での負の整数の表現や減算の実装などによく用いられる。

数値を表すビット列のうち、何ビット目までが整数部で、何ビット目からが小数部かがあらかじめ固定・指定されている形式である。整数は小数点の位置が右端に固定されている特殊な場合の固定小数点数と考えることができる。

これに対し、ビット列全体を、正負を表す符号部、スケールを表す指数部、各桁の数の並びを表現する仮数部の3つに分け、基数(多くの場合2や10)を指数でべき乗した値を仮数にかけて数値を表現する方式を「浮動小数点数」(floating-point number)という。

固定小数点数は浮動小数点数に比べ表現できる値の範囲が狭く、計算の精度が低いが、整数と同じ原理や回路を用いて高速に計算できる。大きさが極端に違う数値の加減算で小さい値の情報が無視されてしまう「情報落ち」が起こらないという特徴もある。

汎用的な数値計算などでは浮動小数点数を用いるのが普通だが、3次元コンピュータグラフィックス(3DCG)の座標計算やDSP(デジタルシグナルプロセッサ)の信号処理など、扱う値の幅が決まっており高速性が重要な用途では計算の高速化のために固定小数点数が好まれることがある。

一つの数値を符号部(正負)、仮数部、指数部の3つのデータの組み合わせで表現(データ形式としては符号-指数-仮数の順に格納することが多い)する。仮数に基数(通常は2)を指数乗した値を乗じ、符号を付け加えたものが表現する数値となる。

例えば、「-4.375」は2進数では「-100.011」であり、仮数と指数に分離すると「-1.00011×10¹⁰」(値はすべて2進表記)となる。符号は正を0、負を1とすることが多いため、符号部の値は「1」、仮数部の値は「100011」、指数部の値は「10」となる。数値が0の場合は符号と指数は不定となるが、便宜上各部をすべて0としたもの(+0.0×10⁰)を0の表現として扱うことが多い。

IEEE 754形式

浮動小数点数は全体のデータ長や仮数部と指数部のビット数の配分などで様々な形式が存在するが、広く普及している標準規格としてIEEE 754形式が知られる。

全体で16ビット(符号1+指数5+仮数10)の「半精度浮動小数点数」、32ビット(符号1+指数8+仮数23)の「単精度浮動小数点数」、64ビット(符号1+指数11+仮数52)の「倍精度浮動小数点数」、128ビット(符号1+指数15+仮数112)の「四倍精度浮動小数点数」の4つの形式が定められており、それぞれ表現できる数値の幅の異なる。実用上は単精度と倍精度がよく用いられ、プログラミング言語や論理回路などでもこの2つに標準で対応しているものが多い。

仮数の2進数表現は先頭が必ず1になる(2以上の数字は使わない)ため、これを省略して代わりに下位の桁の表現に回す手法(俗にケチ表現という)が用いられる。また、指数部を符号なし整数とするため、本来の値に最大値の半分-1を足した表現(俗にゲタ履き表現という)を用いる。例えば指数部が8ビットの場合は127を加え、128が1を、126が-1を表す。

単精度浮動小数点数 (single precision floating point number)

数値を仮数部と指数部に分けて表現する浮動小数点数の形式の一つで、一つの数値を32ビットのデータで表現する方式のこと。多くのプログラミング言語などでは単に浮動小数点といえば単精度を意味し、“float” などの名称で表されるデータ型が用意されている。

IEEE 754標準で規定された形式では32ビットのうち先頭1ビットが正負の符号部(0が正、1が負)、続く7ビットが指数部(基数は2)、残り24ビットが仮数部となる。表現できる値の大きさの範囲は十進表記で約1.2×10^-38～約3.4×10³⁸であり、精度は十進7桁程度となる。

倍精度浮動小数点数 (double precision floating point number)

数値を仮数部と指数部に分けて表現する浮動小数点数の形式の一つで、一つの数値を64ビットのデータで表現する方式のこと。多くのプログラミング言語などが高精度な数値計算のために組み込みデータ型として用意しており、 “double” などの名称で表される。

IEEE 754標準で規定された形式では64ビットのうち先頭1ビットが正負の符号部(0が正、1が負)、続く11ビットが指数部(基数は2)、残り52ビットが仮数部となる。表現できる値の大きさの範囲は十進表記で約2.2×10^-308～約1.8×10³⁰⁸であり、精度は十進16桁程度となる。

一つの数値を符号部(正負)、仮数部、指数部の3つのデータの組み合わせで表現(データ形式としては符号-指数-仮数の順に格納することが多い)する。仮数に基数(通常は2)を指数乗した値を乗じ、符号を付け加えたものが表現する数値となる。

例えば、「-4.375」は2進数では「-100.011」であり、仮数と指数に分離すると「-1.00011×10¹⁰」(値はすべて2進表記)となる。符号は正を0、負を1とすることが多いため、符号部の値は「1」、仮数部の値は「100011」、指数部の値は「10」となる。数値が0の場合は符号と指数は不定となるが、便宜上各部をすべて0としたもの(+0.0×10⁰)を0の表現として扱うことが多い。

IEEE 754形式

浮動小数点数は全体のデータ長や仮数部と指数部のビット数の配分などで様々な形式が存在するが、広く普及している標準規格としてIEEE 754形式が知られる。

全体で16ビット(符号1+指数5+仮数10)の「半精度浮動小数点数」、32ビット(符号1+指数8+仮数23)の「単精度浮動小数点数」、64ビット(符号1+指数11+仮数52)の「倍精度浮動小数点数」、128ビット(符号1+指数15+仮数112)の「四倍精度浮動小数点数」の4つの形式が定められており、それぞれ表現できる数値の幅の異なる。実用上は単精度と倍精度がよく用いられ、プログラミング言語や論理回路などでもこの2つに標準で対応しているものが多い。

仮数の2進数表現は先頭が必ず1になる(2以上の数字は使わない)ため、これを省略して代わりに下位の桁の表現に回す手法(俗にケチ表現という)が用いられる。また、指数部を符号なし整数とするため、本来の値に最大値の半分-1を足した表現(俗にゲタ履き表現という)を用いる。例えば指数部が8ビットの場合は127を加え、128が1を、126が-1を表す。

単精度浮動小数点数 (single precision floating point number)

数値を仮数部と指数部に分けて表現する浮動小数点数の形式の一つで、一つの数値を32ビットのデータで表現する方式のこと。多くのプログラミング言語などでは単に浮動小数点といえば単精度を意味し、“float” などの名称で表されるデータ型が用意されている。

IEEE 754標準で規定された形式では32ビットのうち先頭1ビットが正負の符号部(0が正、1が負)、続く7ビットが指数部(基数は2)、残り24ビットが仮数部となる。表現できる値の大きさの範囲は十進表記で約1.2×10^-38～約3.4×10³⁸であり、精度は十進7桁程度となる。

倍精度浮動小数点数 (double precision floating point number)

数値を仮数部と指数部に分けて表現する浮動小数点数の形式の一つで、一つの数値を64ビットのデータで表現する方式のこと。多くのプログラミング言語などが高精度な数値計算のために組み込みデータ型として用意しており、 “double” などの名称で表される。

IEEE 754標準で規定された形式では64ビットのうち先頭1ビットが正負の符号部(0が正、1が負)、続く11ビットが指数部(基数は2)、残り52ビットが仮数部となる。表現できる値の大きさの範囲は十進表記で約2.2×10^-308～約1.8×10³⁰⁸であり、精度は十進16桁程度となる。

浮動小数点数はコンピュータで数(実数)を表す際によく用いられる表現形式で、実数部分と小数部分に割り当てる桁数をある範囲で任意に変動させることができる。数自体の大きさによらず常に同じ精度で数値を表現することができる。

浮動小数点表現では、数を「仮数×基数^指数」という形式で表現する。分かりやすさのため仮数を十進数、基数を10とすると、例えば「573.765」という数は「5.73765×10^2>という形で表すことができる。仮数は「5.73765」と指数「2」となる。

仮数における小数点の位置はどこでもよく、表現形式の規約などで決めておく必要がある。先の例は仮数を整数で表すことも可能で、その場合は「573765×10^-3」という表現になり、仮数は「573765」、指数「-3」となる。

コンピュータ上ではすべての情報を「0」と「1」の組み合わせで表すデジタルデータを用いる関係上、仮数も指数も2進数で表し、基数にも2を用いることが多い。浮動小数点数の形式を定めた標準規格のIEEE 754では基数2の形式と基数10の形式が用意されている。

冪乗の指数 (exponent)

数学では、ある数aを $a\times a\times \dots \times a$ とn回(nは正の整数)掛ける演算を冪乗と呼び、aの右肩に小さくnを置いた $a^n$ と表記する。このとき、aを「底てい」、nを「指数」(exponent)という。

nが0のときは冪乗の値は底によらず0となり($a^0=1$)、nが負のときは1をaでn回割った数(正の場合の逆数)となる。また、指数が整数の逆数の場合は冪根を表す。例えば、整数mについて$a^{\frac{1}{m}}$ はaのm乗根 $\sqrt[m]{a}$ (m回掛けるとaになる数)を表す。

指標としての指数 (index)

他の分野では、対象の状態やその変化をよく表す数値のことを指数(indexまたはfactor)ということが多い。特に、それ自体は直接的には何らかの物理量などを表すわけではない指標のことを指数と呼ぶ例が多い。知能指数、不快指数、暑さ指数など分野によって様々な種類がある。

経済の分野では、物価や賃金などの推移を表す際に過去の特定時点を100とした比率で表したものを「賃金指数」「物価指数」といったように呼ぶ。また、直接的な数値での把握が難しい景況などについて、アンケートで「良い」と答えた回答の数から「悪い」の数を引いた数値の推移で表したものを「景気動向指数」(DI：Diffusion Index)という。

BCDでは10進数の「0」から「9」の数字を2進数の「0000」から「1001」に対応させ、これを連ねて数値を表現する。4桁の2進数は本来0から15までの10進数を表現できるが、10(1010)から15(1111)までは使わない。

BCDの拡張仕様に「パック10進数」と「ゾーン10進数」(アンパック10進数)がある。前者は1バイト(8ビット)のデータを4ビットずつに区切って2桁の10進数を表現する方式で、最後に値の正負を表す特殊なコード(機種によるが多くの場合は12が正、13が負)が付加される。1バイトに2桁ずつ格納でき効率的である。

ゾーン10進数は1バイトで10進数の1桁を表現する方式で、前半4ビットを文字であるか数値であるかを識別する「ゾーン部」、後半4ビットを値の表現に用いる。最後に正負の符号コードを付加する。記憶容量の利用効率は低いが文字と数字を同じ符号体系で取り扱うことできる。

10進数における1桁の数字(0～9)を4桁の2進数(4ビットのバイナリデータ)に対応させ、「0000」(0)から「1001」(9)までのビットパターンで置き換える。これを2つ連ねて1バイト(8ビット)のデータを構成する。

末尾の4ビットは正負の符号を表すコードで、通常は正を「1100」(12)、負を「1101」(13)とするが、一部の機種や処理系では異なる値が用いられることもある。符号を含めて奇数桁の場合は最上位に「0000」を追加して全体が整数バイトになるよう調整する。

ほとんどの言語では加減算は算術・数学と同じ「+」「-」を用いる。半角文字(ASCII文字)には乗算記号「×」と除算記号「÷」が用意されていないため、それぞれ「*」(アスタリスク)、「/」(スラッシュ)で代用することが多い。

一般の算術にはない記号として、剰余(割り算の余り)を求める演算子(C言語系の「%」など)や、累乗を求める演算子(BASIC系の「^」、PythonやJavaScriptの「**」など)が用意されている言語もある。

整数型の変数の値に1を加算するインクリメント演算子(C言語系の「++」など)や、同じく1を減算するデクリメント演算子(同「--」など)を算術演算に分類する場合もある。

数値の足し算(add：加算/加法)、引き算(subtract：減算/減法)、掛け算(multiply：乗算/乗法)、割り算(divide：除算/除法)の4つを合わせてこのように総称する。

それぞれの計算の結果を「和」(sum)、「差」(difference)、「積」(product)、「商」(quotient)という。除算では商の他に、割り切れないときの「余り」である「剰余」(remainder)を出すこともある。

算術の計算式ではそれぞれ「＋」「－」「×」「÷」の演算子で表すが、「×」は「・」で代用することもある。除算記号が「÷」の国は日米英中韓など少数派で、世界的には「／」(スラッシュ)で表す国が多い。剰余は「5÷2＝2…1」のように商の後に「…」を付けて記載する。

コンピュータ上での表記

コンピュータ上では、ASCIIなど欧米の文字コード標準には「×」や「÷」が存在せず、乗算を「*」(アスタリスク)、除算を「/」(スラッシュ)で表すのが一般的となっている。プログラミングで用いられる「整数除算の剰余を求める演算」(剰余演算)は「%」で表されることが多い。

プログラミング言語や表計算ソフトの関数、CPUの命令セットなどでは、記号ではなく英略語で各演算を表すことがある。それぞれを表す単語を元に、加算を「add」や「sum」、減算を「sub」や「diff」、乗算を「mul」や「prod」、除算を「div」(または商を「quot」余剰を「rem」や「mod」)といった略号で表すことが多い。

マイクロプロセッサなどが実行できる最も基本的な演算の一つで、加減算よりも単純な論理回路で実現でき高速に実行することができるため、様々なデータ処理・計算の一部としてよく用いられる。

ほとんどのプロセッサはシフト演算を行うための命令語が用意されており、アセンブリ言語にも対応する命令が存在する。また、多くのプログラミング言語にも加減算などと共にシフト演算のための演算子などが用意されている。

右シフトと左シフト

ビット列全体を下位ビット側に移動することを右シフト、上位ビット側に移動することを左シフトという。移動の結果、端からあふれた値は消滅し、反対側から同じだけ0(算術右シフトでは符号ビットのコピー)が挿入される。CPU内部の処理として、あふれたビットの値をキャリーフラグに代入する動作が行われることもある。

ビット列が整数を表す場合、右へ1ビット移動するごとに値が半分になり、左へ1ビット移動するごとに値が2倍になる。複数ビット移動すると2のべき乗倍あるいは2のべき乗分の1を得ることができる。この性質を利用して、算術演算の実装の一部にシフト演算が組み込まれる場合がある。

算術シフトと論理シフト

最上位ビットは変化させず残りのビット列でシフトを行うものを「算術シフト」(arithmetic shift)、全ビットを一律に移動させるものを「論理シフト」(logical shift)という。

前者は最上位ビットを符号ビットとして符号付き整数を表現する場合に、負数でもシフトによって2のべき乗の乗算を行うことができる。例えば、「1010」を右に1ビット論理シフトすると左端に0が補充され「0101」になるが、右に1ビット算術シフトする場合は符号ビットのコピーが補充され「1101」となる。

ビットシフト操作はビット列を右または左に指定の数だけ移動する操作だが、論理シフトでは最上位ビットも他の残りのビットと区別せず、ビット列全体を左右に移動させる。移動する方向と反対側に新たに現れるビットには「0」を補充する。

コンピュータでは負の数を表現したい場合に、最上位ビットと正負の符号を表す符号ビットとして、0または正なら「0」、負なら「1」とする規則を用いることが多いが、論理シフトは符号ビットを特別視せず移動してしまうため、符号付き整数の算術的な演算に用いることはできない。

例えば、「10011100」を右に2ビットシフトすると「00100111」となる。これらのビット列を符号付き整数とみなした場合、「10011100」は十進数で「-25」だが、「00111001」は「57」となる。正の数を右に2ビットシフトすると4で割るのと同じ効果があるが、負の数では算術計算は成り立たない。

一方、最上位ビットを固定して変化させず、残りのビットを左右に移動させる処理を行うビットシフト操作を「算術シフト」(arithmetic shift)という。左にシフトする場合は右端に「0」を補充するが、右にシフトする場合は左端に符号ビットの値(負なら「1」)を補充する。これにより、負の数をシフトしたときも1ビット移動するごとに2倍あるいは1/2倍となることが保証される。

コンピュータで負数も表現できる符号付き整数をビット列で表す場合、最上位ビットを符号ビットとして、これが「0」なら0または正、「1」なら負という規則で値の正負を表す。

ビットシフト操作はビット列を右または左に指定の数だけ移動する操作だが、算術シフトでは最上位ビットの値は変更せず、2番目から最下位ビットまでを左右に移動する。左シフトの場合は下位側に「0」を、右シフトの場合は上位側に符号ビットの値を補充する。

例えば、「11100111」(-25)を左に2ビットシフトすると、最上位の「1」は変わらず、続く上位ビットが2桁ずつ左に移動して「00111」となり、末尾に「0」が2桁補充されて「10011100」(-100)となる。正の数の2ビット左シフトと同じように算術的に元の数の4倍となっている。

また、「10101000」(-88)を右に2ビットシフトすると、やはり最上位の「1」は変わらず、下位側が2桁ずつ右に移動して「01010」となり、空いた上位側に符号ビットの「1」が2桁補充されて「111010101」(-22)となる。正の数の2ビット右シフトと同じように算術的に元の数の1/4倍となっている。

一方、ビットシフト操作のうち符号ビットを考慮せず全ビット一律に左右に移動する操作のことを「論理シフト」(logical shift)という。ビット列が符号付き整数を表す場合には負数の算術的な計算ができないが、正の数しか扱わない符号なし整数や数値以外のデータのシフト操作に適している。

長い桁の小数や無限小数を数値計算する場合には、ある桁以降の値を四捨五入するなどして有限桁で表す(丸める)ことがあるが、丸めた後の値が非常に近い値同士で減算を行うと差が非常に小さい値となり、計算前の値より有効な桁が大きく減少してしまうことがある。

例えば、√100001-√100000 という計算を有効数字8桁で行うと 0.31622935×10³-0.31622777×10³ = 0.158×10^-2 となってしまい、得られた結果の有効な桁は3桁に減少してしまう。

コンピュータの浮動小数点形式では便宜上、計算の結果失われた下位の桁を0で埋めて 0.15800000×10^-2 のように扱うため、これに大きな数を掛けるなど続けて計算していくことで、途中で生じた桁の欠落が最終的に大きな誤差を生じさせてしまうことがある。

コンピュータでは扱う数値の桁数に制限があるため、極端に大きな値と極端に小さな値を加減算すると計算結果の数値は桁数が非常に長くなってしまい、小さい値に由来する部分がすべて切り捨てられてしまう。

単純に2つの数値の和を求めるような場合であれば大した影響は無いが、大きさの極端に異なる値がたくさんあり、加算を繰り返してすべての合計を求めるような状況では、落差の大きい組み合わせの加算で常に小さい値が無視されてしまい、最終的な結果が大きく狂ってしまうことがある。

そのような場合には、値を小さい順に並べて小さい方から順に足し合わせるといった処理を行うことで、情報落ちの影響を小さくすることができる。

算術オーバーフロー

コンピュータ内部で一般的な数値データを格納するメインメモリ上の領域やCPU内部のレジスタは、一つの数値を決まったデータ量で表すようにできており、取り扱える数値の大きさや桁数に上限がある。

数値を計算した結果がこの上限を超え、正しく格納・表現できなくなってしまうことを「オーバーフロー」という。例えば、1バイトの符号なし整数型は0から255までの整数を表現できるため、「150×2」という計算の結果を格納しようとすると上限を超えてしまいオーバーフローとなる。

オーバーフローが発生した際の対処方法として、例外を引き起こして例外処理ルーチンによって何らかの対処を行う場合、実行時エラーを出力してプログラムを停止する場合、表現可能な上限値を設定する場合、上限を超えたことを示す特殊な値を格納する場合、単に無視する場合などがある。

オーバーフローを無視してそのまま処理を続行した場合、あふれた上位の桁が消滅して奇妙な値が計算結果となったり、メモリ領域上の隣接する無関係の区画にあふれた数値データの一部を書き込んで内容を破損させてしまうといった事象が起きる場合もある。

負数や浮動小数点数の場合

オーバーフローが起きるかどうかは桁の大きさの問題であるため、符号付き整数の場合には負数の値が下限を超えた場合(絶対値の桁数が上限を超えた場合)にも発生する。また、浮動小数点の場合には指数部の大きさが上限値よりも大きくなった場合にそれ以上大きな値を表すことができずオーバーフローとなる。

アンダーフロー(underflow)

浮動小数点数において、値の絶対値が小さくなりすぎ(小数点以下の0の桁数が長くなりすぎ)て正しく値を表現できなくなる現象を「アンダーフロー」(underflow)という。指数部が下限値より小さくなることで発生し、0に置き換えられてしまうことで除算や乗算の結果が大きく狂うといったことが起きる。

メモリ領域のオーバーフロー

外部からデータを受け取ってメモリ上の領域に保存するようなプログラムで、指定された領域のサイズを超えてデータを受け取ってしまい、隣接する別の区画にデータをあふれさせてしまうことを「オーバーフロー」あるいは「オーバーラン」(overrun)ということがある。

無関係の領域にデータを書き込んでしまうことにより、処理が停止したり、予期しない動作が発生することがある。バッファ領域について発生するものを「バッファオーバーフロー」、スタック領域について発生するものを「スタックオーバーフロー」という。

ネットワークを通じて外部からコンピュータを乗っ取る攻撃手法の一つとして、不正なデータを送りつけて受信プログラムにわざとオーバーフローを発生させ、攻撃用のプログラムコードを実行するよう仕向ける手法があり、「バッファオーバーフロー攻撃」と呼ばれる。

コンピュータでは実数を浮動小数点数という形式で表すが、一つの値を表すためのデータ長が決まっており、表現できる値の範囲も限られている。計算結果の絶対値が表現可能な最小の値より小さくなってしまうことをアンダーフローという。

例えば、一つの値を32ビットのデータで表す単精度浮動小数点数(float型)では、表現できる値の範囲は十進表記で約1.2×10^-38～約3.4×10³⁸であるため、指数部が10^-39を下回る場合には正しく値を表現できなくなる。

実際にアンダーフローが生じた際の動作はプログラミング言語や処理系によっても異なるが、仮数部を規定(通常は仮数の先頭が1になるよう正規化される)よりも小さくすることで表現できる範囲では、指数部を下限値にしたまま仮数部の先頭から0を詰めていく処理が行われる場合がある。

さらに値が小さくなっていき、仮数部の桁を使い切ってしまうと、どうやってもそのような値は表現することができないため、値が完全に0になってしまうことが多い。除算を組み合わせた計算の途中でアンダーフローが起きると、意図せずゼロ除算が生じて実行時エラーとなってしまう場合があるため注意が必要である。

負数のオーバーフロー

よく勘違いされるが、負の数が表現可能な下限を超え、正しく値を表現できなくなるのは「オーバーフロー」(桁あふれ)の一種である。絶対値が表現可能な上限を超えることによって発生し、下限より小さくなるアンダーフローとは区別される。

小数点数以下の桁数が可変であるような実数値を表現することができる浮動小数点数型の一つで、一つの数値を32ビットの長さのデータとして表す。

C言語やその影響を受けた言語では “float” (フロート)という型名が用いられるが、他に “single”(シングル)や “real”(リアル)などの型名もよく用いられる。Pythonのようにfloat型がいわゆる倍精度(64ビット長)を表す場合もあるため注意を要する。

表現形式は言語仕様などにより異なるが、標準規格として普及しているIEEE 754のbinary32形式の場合、先頭から1ビットの符号部(正負を表す)、8ビットの指数部(小数点の位置を示す)、23ビットの仮数部(桁の並びを表す)の順に格納する。仮数の先頭の「1」は正規化により省略されるため、実質的には24ビットで仮数を表す。

この形式で表すことができる値は十進数で概ね -3.40282×10³⁸～3.40282×10³⁸ の範囲で、精度は6桁である。

小数点数以下の桁数が可変であるような実数値を表現することができる浮動小数点数型の一つで、一つの数値を64ビットの長さのデータとして表す。C言語やその影響を受けた言語では “double” (ダブル)という型名が用いられることが多い。

表現形式は言語仕様などにより異なるが、標準規格として普及しているIEEE 754のbinary64形式の場合、先頭から1ビットの符号部(正負を表す)、11ビットの指数部(小数点の位置を示す)、52ビットの仮数部(桁の並びを表す)の順に格納する。仮数の先頭の「1」は正規化により省略されるため、実質的には53ビットで仮数を表す。

この形式で表すことができる値は十進数で概ね -1.79769×10³⁰⁸～1.79769×10³⁰⁸ の範囲で、精度は15桁である。

19世紀の終わり頃、イギリスの数学者ジョン・ベン(John Venn)によって考案された図法である。まず大きな長方形などで描画範囲を設定し、これをすべての要素が含まれる全体集合とする(この領域は設定しない場合もある)。個々の集合は円や楕円などの図形で表される。集合間に共通の要素がある場合、図形の一部を重ねて表現する。

集合Aを円で表すとき、Aの外側はAの補集合(A、A^c)を表す。集合Bも円で表すと、両者の重なった領域が共通部分(A∩B)、重なりも含め両者を合わせた領域が和集合(A∪B)を表す。BがAに完全に含まれる場合、BはAの部分集合(A⊃B)となる。

3つ以上の集合の関係も図示できるが、4つ以上は重なり方の組み合わせを漏らさず図示するのが難しくなるため、あまり用いられない。説明のために集合ごとに色や模様で塗り分けたり、現在着目している領域のみを着色することが多い。黒で塗られた領域は元が存在しないことを表すため、塗り分けで黒を用いることは控える。

集合演算の結果を視覚的に分かりやすく表すことができるため、これを論理演算の図示に応用することもある。変数を円に対応付け、円の内部を真(true)または1、外側を偽(false)または0に対応付ける。例えば、2変数PとQの場合、円Pの外側がPの論理否定(not P/￢P)、円の重なりが論理積(P and Q/P∧Q)、両円を合わせた領域が論理和(P or Q/P∨Q)に対応する。

数学の集合論で用いられる概念で、集合Aと集合Bの少なくとも一方に含まれる元全体から成る集合を「AとBの和集合」と呼び、「A∪B」と書き表す。演算としては整数などの加算と同じように、交換法則、結合法則、分配法則が成り立つ。

AとBに共通の元がない場合は「直和」(direct sum)あるいは「非交和」(disjoint union)とも呼ばれる。例えば、Aが奇数の集合、Bが偶数の集合の場合、両者の間に交わりは無く、自然数の集合であるA∪Bは直和となる。

数学の集合論で用いられる概念で、集合Aに含まれる元 { a₁, a₂, a₃, … } と集合Bに含まれる元 { b₁, b₂, b₃, … } を一つずつ使って (a₁,b₁) といった値の組を作り、そのすべての組み合わせを元とする集合である。

この値の組は値の登場順も区別する順序対と呼ばれるもので、(1,2)と(2,1)は異なる組であるとみなされる。このため、一般にA×BとB×Aは必ずしも一致するとは限らず、演算として「項の前後を入れ替えても同じ結果」になるという交換法則は成り立たない。

積集合の例としてよく知られるのはトランプの図柄で、4つの絵柄(スート) { ♠, ♥, ♦, ♣ } の集合と、13のランク(数字・文字) { A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K } の集合のすべての元の組み合わせで52枚(4×13)の絵柄が構成されている。

積集合は「直積」「積」「デカルト積」「積集合」などとも呼ばれるが、「積集合」は複数の集合のすべてに所属する元から成る集合(論理演算の論理積に相当)を指すこともある。積集合との混同を避けるため、こちらは「共通集合」「共通部分」等と呼ばれることもある。

数学の集合論で用いられる概念で、全体集合Uに含まれる要素のうち、ある集合Aの要素を除いた残りの要素を集めた集合を「Aの補集合」と呼び、「A」あるいは「A^c」のように記す。

例えば、Uが整数の集合、Aが奇数の集合であれば、Aは偶数の集合となる。AとAの補集合の共通集合は空集合であり(A∩A=∅)、和集合は全体集合に等しくなる(A∪A=U)。

数学の集合論で用いられる概念で、集合Bの元がすべて集合Aの元でもあるとき、BはAの部分集合であると言い、「A⊇B」のように表す。BはAに含まれる、包含される、包まれる、包摂される、内包されるなどと表現することもある。このとき、AをBの上位集合(superset)であるという。

例えば、三つの元から成る集合A={a, b, c}があるとき、一つまたは二つの元から成る {a}{b}{c}{a, b}{b, c}{a, c} は部分集合である。また、{a, b, c}、すなわちA自身と、何の元も含まない空集合∅もAの部分集合に含まれる。

AがBを含み、かつAにはBに属さない元も存在する(つまり、AとBは同じ集合ではない)場合、BはAの真部分集合(proper subset)であると言い、等号を含まない記号を用いて「A⊃B」のように表す。このとき、AはBの真上位集合(proper superset)であると言う。

プログラミング言語などにも命題の真偽を表す仕組みや表記法が用意されていることがあり、真あるいはブール値(boolean value)などと呼ぶ。条件式や論理演算(ブール演算)の結果を表すことができ、真を表すことができるデータ型を論理型、ブーリアン型(ブール型)などという。

リテラルの表記は言語によって異なるが、真は「true」「True」「TRUE」などと、偽は「false」「False」「FALSE」などと表記することが多い。真に相当する値を整数で代用し、0が偽、0以外が真とする言語や処理系もある。

電子回路などの場合には、真を1ビットの値の0と1に対応付け、電流のオンとオフ、電圧の高低、電荷の有無などの物理量で表す。デジタル信号の1を真、0を偽に対応付けるのが一般的。

プログラミング言語などにも命題の真偽を表す仕組みや表記法が用意されていることがあり、偽あるいはブール値(boolean value)などと呼ぶ。条件式や論理演算(ブール演算)の結果を表すことができ、偽を表すことができるデータ型を論理型、ブーリアン型(ブール型)などという。

リテラルの表記は言語によって異なるが、真は「true」「True」「TRUE」などと、偽は「false」「False」「FALSE」などと表記することが多い。偽に相当する値を整数で代用し、0が偽、0以外が真とする言語や処理系もある。

電子回路などの場合には、偽を1ビットの値の0と1に対応付け、電流のオンとオフ、電圧の高低、電荷の有無などの物理量で表す。デジタル信号の1を真、0を偽に対応付けるのが一般的。

入力が一つの単項演算として、入力値の反対の値を出力する「否定」(NOT A：Aではない)がある。入力が二つの二項演算には、どちらかが真なら真を出力する「論理和」(A OR B：AまたはB)、両者とも真の時のみ真を出力する「論理積」(A AND B：AかつB)、両者が異なる時に真を出力する「排他的論理和」(XOR：eXclusive OR)がある。

電子回路などでは、論理和と否定を組み合わせた「否定論理和」(NOR：Not OR)、論理積と否定を組み合わせた「否定論理積」(NAND：Not AND)が用いられることもある。排他的論理和と否定を組み合わせた「否定排他的論理和」(XNOR)は値が同じとき真、異なるとき偽となるため「同値」(EQ：equal)とも呼ばれる。

三項以上を計算する際は二項ずつの計算を繰り返すことで結果が得られる。その際、四則演算のように交換法則や分配法則、結合法則、ド・モルガンの法則などが成り立つ。すべての論理演算はNOT、AND、ORの三つの組み合わせで構成できるが、この三つはすべてNANDの組み合わせで構成でき、NANDだけですべての論理演算を記述できることが知られている。

コンピュータでは真偽値自体の演算(プログラミング言語におけるブール型の値の演算など)の他に、真を1、偽を0に置き換えてビット間で論理演算を行うことがある。ビット列について論理演算を行う場合は二つのビット列のぞれぞれ対応する位置にあるビット同士で論理演算を行う。

このような演算方式を真偽値の論理演算と区別して「ビット演算」(bitwise operation)と呼ぶこともある。なお、ビット演算には論理演算に相当する演算以外にも、シフト演算やローテート演算などビット列を左右に移動する操作もある。

プログラミング言語では算術演算などと並んで最も基本的な演算の一つとして論理演算が用意されていることが多く、論理演算子によって式を記述する。演算子は「&&」のような記号を用いる場合と、「and」のような英単語をそのまま用いる場合がある。C言語の「&」と「&&」のように、論理演算と対応するビット演算にはそれぞれ別の演算子が与えられていることが多い。

A AND B という式全体の否定である NOT( A AND B ) は、個別の値の否定である NOT A と NOT B をORで繋いだ (NOT A) AND (NOT B) に等しくなる。この関係はANDとORを入れ替えた NOT(A OR B) と (NOT A) AND (NOT B) の間にも成り立つ。

集合演算の場合は和集合(∪)と積集合(∩)の関係について、A∩B=A∪B および A∪B=A∩B という関係が成り立つ。論理演算の場合は論理和(∨)と論理積(∧)の関係について、￢(P∧Q)=￢P∨￢Q および ￢(P∨Q)=￢P∧￢Q という関係が成り立つ。これらの関係は3項以上でも同様に成り立つ。

真理値(ブール値/真偽値)は論理演算などで用いられる値で、「真」(true)と「偽」(false)の2値のいずれかを取る値である。コンピュータ上ではすべての情報を「1」と「0」を並べた2進数で表すため、真と1を、偽と0を対応付けて論理回路で様々な処理を行う。

真理値表は論理演算の入力値と出力値の対応関係を図に表したもので、一般的な形式では表の左側の列に入力を、右側の列に出力をそれぞれ並べる。各行に入力の組み合わせと、その時の出力を記入していく。各項には「1」(あるいは「真」「Truth」「T」)か「0」(あるいは「偽」「False」「F」)のどちらかを記入する。

行数

入力が1つ(NOT演算)の場合は入力「0」と「1」の2行で表され、入力が2つの場合は「0-0」「0-1」「1-0」「1-1」の4行となる。同様に、3入力では8行、4入力では16行というように、2の入力数乗が表の行数となる。

列数

ある特定の論理演算の結果を示す場合は出力は1列となるが、複数の異なる演算について結果を比較するために、それぞれの演算ごとに列を用意する(列名部分に演算内容を記述する)場合もある。論理回路の動作を示す表の場合には、出力の数だけ列を用意し、それぞれの演算結果を書き込んでいく。

論理学では記号「¬」を用いて「P¬Q」のように表記し、電子工学(論理回路)では記号「¯」(上線)を用いて「P」のように表す。論理否定演算を行う論理回路を「否定演算回路」「NOT演算回路」「NOTゲート」などと呼ぶ。

多くのプログラミング言語でもビットごとの論理否定演算(ビット反転)を行う演算子が用意されており、キーワード「not」を用いて「not p」のように書くものや、C言語などの記法にならって「~」(チルダ)記号を用いて「~p」のように表記する言語が多い。

ビット演算と区別して条件式などで用いる真偽値(真理値)の論理否定演算を定義している言語では、「not」キーワードや「!」などの演算子が用いられることが多い。いずれの場合も、演算の対象となる被演算子(オペランド)が一つの単項演算子である。

論理学では記号「∨」を用いて「P∨Q」のように表記し、電子工学(論理回路)では記号「+」を用いて「P+Q」のように表す。論理和演算を行う論理回路を「論理和演算回路」「OR演算回路」「ORゲート」などと呼ぶ。

多くのプログラミング言語でもビットごとの論理和演算を行う演算子が用意されており、キーワード「or」を用いて「P or Q」と書くものや、C言語に倣って「|」記号を用いて「P|Q」と表記する言語が多い。また、ビット演算と区別して条件式などで用いる真偽値(真理値)の論理和演算を定義している言語では、「or」キーワードや「||」などの記号が用いられることが多い。

三入力以上の場合は、まず二つを選んで論理和を取り、その結果と残りの一つを選んで論理和を取り、という手順を繰り返すことで結果を得ることができ、いずれかの入力が1のときに出力が1となり、すべての入力が0の場合に0となる。

論理和は論理積(AND演算)と論理否定(NOT演算)を組み合わせて P∨Q ⇔ ¬(¬P∧¬Q) と表すことができる。逆に、論理積は論理和と論理否定を組み合わせて P∧Q ⇔ ¬(¬P∨¬Q) と表すことができる。これをド・モルガンの法則という。

論理学では記号「∧」を用いて「P∧Q」のように表記し、電子工学(論理回路)では記号「⋅」を用いて「P⋅Q」のように表す。論理積演算を行う論理回路を「論理積演算回路」「AND演算回路」「ANDゲート」などと呼ぶ。

多くのプログラミング言語でもビットごとの論理積演算を行う演算子が用意されており、キーワード「and」を用いて「P and Q」と書くものや、C言語に倣って「&」(アンパサンド)記号を用いて「P&Q」と表記する言語が多い。また、ビット演算と区別して条件式などで用いる真偽値(真理値)の論理積演算を定義している言語では、「and」キーワードや「&&」などの記号が用いられることが多い。

三入力以上の場合は、まず二つを選んで論理積を取り、その結果と残りの一つを選んで論理積を取り、という手順を繰り返すことで結果を得ることができ、すべての入力が1のときのみ出力が1となり、いずれかの入力が0の場合には0となる。

論理積は論理和(OR演算)と論理否定(NOT演算)を組み合わせて P∧Q ⇔ ¬(¬P∨¬Q) と表すことができる。逆に、論理和は論理積と論理否定を組み合わせて P∨Q ⇔ ¬(¬P∧¬Q) と表すことができる。これをド・モルガンの法則という。

論理和(OR演算)に似ているが、論理和では「いずれか一方が真」なら他方が何であれ結果は真となるが、排他的論理和では「いずれか一方のみが真」の場合に真となる。両者共に真の場合は真とならないことを「排他的」と表現している。

三入力以上の場合は、まず二つを選んで排他的論理和を取り、その結果と残りの一つを選んで排他的論理和を取り、という手順を繰り返すことで結果を得ることができる。入力における真の数が奇数個のときに出力が真に、偶数個のとき偽となる。

論理学では記号「⊻」を用いて「P⊻Q」のように表記し、電子工学(論理回路)では記号「⊕」を用いて「P⊕Q」のように表す。排他的論理和演算を行う論理回路を「排他的論理和回路」「XOR回路」「XORゲート」などと呼ぶ。

多くのプログラミング言語でもビットごとの排他的論理和演算を行う演算子が用意されており、キーワード「xor」を用いて「P xor Q」と書くものや、C言語に倣って「^」(ハット、キャレット)記号を用いて「P^Q」と表記する言語が多い。

あるビットが「0」のとき、「1」と排他的論理和を取ると「1」になるが、元の値が「1」なら結果は「0」になる。すなわち、「1と排他的論理和を取る」という演算は「そのビットの値を反転する」という操作になる。これを利用して、反転したい位置を「1」にセットしたビット列を用いて、入力値の特定のビットのみを反転させるという操作がよく用いられる。

三入力以上の場合は、まず二つを選んで否定論理和を取り、その結果と残りの中から一つを選んで否定論理和を取り、という手順を繰り返すことで結果を得ることができ、すべての入力が偽(または0)のときのみ出力が真(または1)となり、いずれかの入力が真(または1)の場合には偽(または0)となる。

論理学では記号「↓」を用いて「P↓Q」のように表記する。電子工学(論理回路)では論理和(OR)の記号「+」と否定(NOT)の記号「¯」(上線)を組み合わせて「P+Q」のように表記することが多い。

否定論理和演算を行う論理回路を「否定論理和演算回路」「NOR演算回路」「NORゲート」などと呼ぶ。AND回路やOR回路、NOT回路、およびこれらを組み合わせた任意の回路は複数のNAND回路の組み合わせによって実現できる「機能的完全性」(functional completeness)という性質がある。

フラッシュメモリの実装方式には、記憶素子をNOR回路によって構成する「NOR型フラッシュメモリ」と、NAND回路(排他的論理積)によって構成する「NAND型フラッシュメモリ」がある。文脈によってはNOR型フラッシュメモリを指して「NOR」と略す場合もある。

三入力以上の場合は、まず二つを選んで否定論理積を取り、その結果と残りの中から一つを選んで否定論理積を取り、という手順を繰り返すことで結果を得ることができ、すべての入力が真(または1)のときのみ出力が偽(または0)となり、いずれかの入力が偽(または0)の場合には真(または1)となる。

論理学では記号「｜」または「↑」を用いて「P｜Q」「P↑Q」などのように表記する。電子工学(論理回路)では論理積(AND)の記号「・」と否定(NOT)の記号「¯」(上線)を組み合わせて「P・Q」のように表記することが多い。

否定論理積演算を行う論理回路を「否定論理積演算回路」「NAND演算回路」「NANDゲート」などと呼ぶ。AND回路やOR回路、NOT回路、およびこれらを組み合わせた任意の回路は複数のNAND回路の組み合わせによって実現できる「機能的完全性」(functional completeness)という性質がある。他の論理ゲートより少ない半導体素子(トランジスタなど)で実装できるため実用上もよく利用される。

フラッシュメモリの実装方式には、記憶素子をNAND回路によって構成する「NAND型フラッシュメモリ」と、NOR回路(否定論理和)によって構成する「NOR型フラッシュメモリ」がある。主流となっているのはNAND型であるため、文脈によってはNAND型フラッシュメモリを指して「NAND」と略す場合もある。

2つの数の和と別の数の積は、それぞれの数と別の数の積を求めて足した和に等しいという法則である。実数や行列などの計算で成り立ち、結合法則や交換法則などと並ぶ最も基本的で重要な法則の一つである。

行列のように積の順番で結果が変わる計算では、$a\times (b+c)=\mathrm{ab}+\mathrm{ac}$ を「左分配則」、$(b+c)\times a=\mathrm{ba}+\mathrm{ca}$ を「右分配則」と呼んで区別する。実数のように順番に意味がない計算では両者は同じことを表しており区別しない。

論理演算では、2つの真偽値の論理和(OR)に対する論理積(AND)で $a\wedge (b\vee c)=\left(\mathrm{a\wedge b}\right)\vee \left(\mathrm{a\wedge c}\right)$ が成り立つほか、論理和と論理積を入れ替えた $a\vee (b\wedge c)=\left(\mathrm{a\vee b}\right)\wedge \left(\mathrm{a\vee c}\right)$ も同じように成立する。

正の整数nについて、1から順にnまでの整数をすべて掛け合わせた積である。例えば、4の階乗「4!」は $4\times 3\times 2\times 1$ で24となる。0!は便宜的に1と定義される。数学では順列、組み合わせの計算で多用される。

平均値、中央値、最頻値が同一の左右対称な分布で、横軸が値、縦軸が確率となるグラフに図示すると釣り鐘のように平均付近が大きく膨らんだ形状(ベルカーブという)となる。誤差や個体差など自然に生まれる値のばらつきの多くは正規分布に従って分布する。

ある値xが出現する確率を表す確率密度関数は、平均値μと標準偏差σを用いて 1/√(2πσ)×e^{-(x-μ)2/2σ2} という式で表される。同じ正規分布でも平均値が異なれば確率が最大になる位置が異なり、標準偏差が異なれば平均への偏り具合が異なる。標本値を線形変換し、平均が0、標準偏差が1になるように調整した分布を「標準正規分布」という。

正規分布の重要な性質として、平均μや標準偏差σの違いによらず、σの倍数で表される区間に値が含まれる確率は常に一定であるというものがある。例えば、平均から標準偏差だけ離れた範囲(μ-σからμ+σまで)に値が含まれる確率は約68.27%、μ±2σの範囲なら約95.45%、μ±3σの範囲なら約99.73%となる。

例えば、ある県に台風が年平均4回上陸する場合、毎年必ず4回上陸するわけではなく、全く上陸しない年もあれば3回、5回といった年もある。このとき、各々の回数になる確率の分布をポアソン分布という。この例では3回と4回をピークに前後が低くなり、0回や9回以上の確率はほとんど0に近くなる。

平均λ回起きる事象が単位時間にk回起きる確率は、自然対数の底e(ネイピア数)を用いて e^-λ λ^k/k! (!は階乗)という式で表される。λおよびその前後が最も確率が高くなり、λから離れるに従って急激に確率は低くなる山型の分布となる。

試行を何度も繰り返したとき、結果を平均するといくつになるかを表したもので、値と値が出る確率の積をすべて足し合わせて求める。例えば、サイコロの1から6が出る確率はすべて $\frac{1}{6}$ で等しいため、期待値は $1\times \frac{1}{6}+2\times \frac{1}{6}+3\times \frac{1}{6}+4\times \frac{1}{6}+5\times \frac{1}{6}+6\times \frac{1}{6}=3.5$ と求めることができる。

賭け事では期待値は得られる儲けの平均額と考えることができる。事業として行われている現実の賭け事では胴元の手数料が差し引かれるため、期待値は負の値(平均的には損をして終わる)となることがほとんどである。

なお、一般に期待値や近い値が最も出現しやすいとは限らない。例えば、宝くじは結果が期待値に近くなる「はずれ」が最も出やすいが、サイコロの出目は期待値が3.5だからといって3と4が最も出やすいわけではない。

数値データの分布を調べるのに用いられるシンプルな表で、データが取りうる値を均等な幅の区間(これを階級という)に分割し、各階級に属するデータを数える。階級と属するデータの数(これを度数という)を2列の表の形でまとめる。

例えば、テストの点数を表にまとめる場合、「0～19点」「20～39点」「40～59点」「60～79点」「80～100点」といった階級に区切り、それぞれに属する人数を数えて「3人」「5人」「7人」「13人」「5人」などのように書き入れていく。

各階級の中央の値「10点」「30点」「50点」「70点」「90点」を、その階級を代表する「階級値」という。階級の幅は任意に決めてよいが、小さすぎると度数の差がつきにくく、大きすぎると度数の変化が大きすぎて分布の様子が分かりにくくなる。

度数分布表をグラフ化したものを「ヒストグラム」(histogram)という。横軸に階級、縦軸に度数を取り、各階級に度数の長さの棒(長方形)を並べて分布の様子を視覚的に表現する。複数の系列を同じグラフに描画して比較したい場合は棒の代わりに折れ線グラフで度数を表現した「度数分布多角形」(frequency polygon)が用いられる。

値の出現頻度の高い階級は高い棒で、低い階級は低い棒で図示されるため、出現頻度の高低やバラつき具合を視覚的に容易に把握できる。各階級の度数を示す棒のことを「ビン」(bin)と呼ぶことがある。

すべてのビンの面積の総和が全体の度数を表しており、各ビンの面積は全体に占めるその階級の度数の割合を視覚的に表現したものとなっている。同じデータ群でも階級の幅の取り方次第でビンの形状や分布は異なるが、どのような基準で区分すべきかについて様々な方法論が提唱されている。

また、手前のすべての区間の度数を足し合わせた累計値をその区間の度数とし、これを右肩上がりの棒グラフの列で示したものを「累積ヒストグラム」(cumulative histogram/累積度数図)という。端からどの区間までが重要かを見極める場合などに利用される。

縦軸に量を取り、横軸方向に系列を箱ひげとして並べていく。各箱ひげは、上のひげの上端が分布の最大値、箱の上端が第3四分位数、箱の中に引かれた仕切り線が第2四分位数(中央値)、箱の下端が第1四分位数、下のひげの下端が最小値となっている。最大値や最小値は外れ値の場合もあるため、ひげの端は最大・最小から1～10%程度の値を用いる場合もある。

一つの箱ひげで一つのデータ系列の分布を直感的に把握することができる。これを系列の数だけ横に並べていくことで、系列間の分布の違いを視覚的に比較することができる。複数の異なる対象の分布を比べるために作成する場合もあれば、同じ対象の時系列の分布の変化を知るために作成することもある。

統計調査などで様々な対象から値を取得すると、様々な大きさの値が集まるが、値全体を要約し、その中心的な傾向を把握することができる一つの値を代表値という。

最もよく用いられるのは「平均値」(average)で、全体の総量が変わらず、すべて同じ値だったらいくつになるかを求めたものである。総量の表し方によりいくつかの種類があるが、最も一般的な「算術平均」(単純平均/相加平均)では、全体の和を値の数で割って求める。

他に、大きい順あるいは小さい順に並べ替えたときに順位がちょうど真ん中の値で代表する「中央値」(median：メジアン/メディアン)や、各値の出現回数(頻度/度数)を数えて最も多く出現する値で代表する「最頻値」(mode：モード)などが用いられる。

平均はすべての値を評価に含めることができるが、少数の極端な値(外れ値)に影響されやすい。中央値は外れ値の影響を受けないが、中央付近の値の変動しか評価しないため時系列の変化を表すのは苦手である。最頻値は値の分布の偏りが小さい(一様に近い)集団が苦手だが、数値で表されないデータ(名義尺度)の集計にも適用できる。

「冬の気温と桜の開花日」や「親の身長と子の身長」のように、傾向として片方が増えるともう片方も増える、あるいは逆に片方が増えるともう片方は減るといった関係性が見られるとき、両者の間に「相関がある」あるいは、両者は「相関関係にある」という。

一方、片方が原因となってもう一方の変化が引き起こされる関係性を「因果関係」という。相関関係は因果関係を含む概念で、因果があれば必ず相関もあるが、相関があるからといって必ずしも因果もあるとは限らない。

統計学では2つのデータ系列の分布について、一方の値が高ければ高いほどもう一方の値も高くなる(同じ方向に連動する)関係を「正の相関」、一方の値が高ければ高いほどもう一方の値は低くなる(逆方向に連動する)という関係を「負の相関」という。

2つのデータ系列の間にどの程度強い相関が見られるかは「相関係数」という値で表すことができる。これは両者が線形相関(1次関数で書き表せる直線的な関係)にどの程度近いかを表す係数で、「1」ならば完全な正の相関、「0」ならば相関なし、「-1」ならば完全な負の相関があることを表す。

測定値などの分布に基づいて、2つの変数の関係を $y=\mathrm{ax}+b$ という一次関数で近似することを単回帰分析という。$x$ を説明変数、$y$ を目的変数と呼び、$x$ の値から未知の $y$ を予測・推測できるようになる。

2つの変数の関係について、横軸を説明変数、縦軸を目的変数とする散布図で表したときに、分布の様子を直線で近似したものを回帰直線という。回帰分析で求めた一次関数(回帰式)をグラフ上に描画したものである。先の方程式の $a$ は直線の傾きを、 $b$ はy切片を表している。

回帰直線は実際のデータを表す各点との距離がなるべく小さくなることが望ましい。この条件を満たすため、一般的には「最小二乗法」という計算法で係数 $a$ と $b$ の値を決定する。説明変数 $x_i$ において、実測された目的変数は $y_i$、回帰式から求めた予測値は $a{x}_i+b$ となる。

両者の差である $y_i-a{x}_i-b$ を2乗し、各点について合計したものを残差平方和という。これが最小になるときの $a$ および $b$ を算出すると、$x$ と $y$ の平均 $\stackrel{-}{x}$ と $\stackrel{-}{y}$ 、標準偏差 $S_x$ と $S_y$ 、相関係数 $r$ を用いて、 $b=r\frac{S_y}{S_x}$ 、 $a=\stackrel{-}{y}-b\stackrel{-}{x}$ として表すことができる。

値を大きい順あるいは小さい順に並べた時、ちょうど真ん中にある値が中央値である。値が偶数個の場合は中央の値が2つになるため、両者の平均値(算術平均)を中央値とする。例えば、「0, 5 ,1, 9, 7」という値の集合がある場合、大きい順でも小さい順でもちょうど3番目が「5」となり、これが中央値となる。

代表値としては値を均した「平均値」(算術平均/相加平均)を用いることが多いが、平均値は極端な値が含まれる場合にその影響を受けやすいという難点がある。例えば、10軒の家があって9軒は車を1台所有しており、残り1軒が11台所有している場合、1軒あたりの平均所有台数は「2台」となるが、実際に2台以上所有しているのは1軒だけである。

このような場合、中央値は5位と6位の中間、すなわち「1台」となり、大半の家が1台のみである実態をよく表している。ただし、時系列の比較などを行う場合、中央値は中央付近の値の動向しか反映しないため、全体の変化の傾向などを表すのには不向きである。

集団の代表値としては平均値、中央値の他にも、同じ値が出現する回数(あるいは区間ごとの頻度)を数え、最も出現頻度が大きいものを取る「最頻値」(mode：モード)を用いることがある。先の車の所有台数の例では最頻値も「1台」である。

集団の中で同じ値が何回出現するかを調べ、最も多く出現する値が最頻値である。例えば、{ 0, 1, 1, 1, 2 } という値の集合があるとき、この中には「0」が1回、「1」が3回、「2」が1回出現しており、最頻値は3回の「1」となる。

連続値の場合は全く同じ値が繰り返し現れることは稀であるため、度数分布表やヒストグラムを用いて「0以上10未満」「10以上20未満」のように区間を区切って頻度を数え、最も多い区間の中心の値(10～20が最多なら15)を最頻値とする。

最頻値は一つに定まるとは限らない。「0, 1, 1, 2, 3, 3, 4」の場合、最多頻度2回の値が「1」と「3」2つとなり、両者ともに最頻値となる。このように最頻値が複数の場合を「多峰性」(multimodal)の分布、中でも2つの場合を「二峰性」(bimodal)の分布という。最も極端な場合、すべての値が同じ頻度で出現するとすべての値が最頻値となる(最頻値を考える意味がなくなる)。

代表値としては他にも、全体を同じ値に均した「平均値」(average)、順位がちょうど真ん中の値を取る「中央値」(median：メジアン、メディアン)などがある。統計値などがきれいな山型の分布にならない場合には、これらより最頻値で代表させるのが適していることがある。また、平均値や中央値と異なり、「○○という回答が最も多かった」というように数値で表されないデータ(名義尺度)の集計にも適用できるという重要な性質がある。

単に平均値という場合はすべての値を足して個数で割った「算術平均」(相加平均、単純平均)を指す。全体の総和は変わらずすべての値が同じだったらいくつになるかを求めたもので、全体の値の水準を表している。

平均値の算出法として、すべての値(n個)を掛け合わせてn乗根を求めることもある。全体の積が同じですべての値が同じだったらいくつになるかを求めたもので、「幾何平均」(相乗平均)と呼ばれる。他にも調和平均、対数平均、加重平均など様々な算出法がある。

平均値は代表値として最もよく用いられるが、値の分布によっては必ずしも全体の性質を表すのに適さない場合がある。例えば、少数の値が極端に大きい(あるいは小さい)と、その値に引きずられてほとんどの値よりずっと大きい(あるいは小さい)値が平均値となることがある。

他によく用いられる代表値として、大きい順に並べ替えたときに順位がちょうど真ん中の値を求める「中央値」(median：メディアン/メジアン)、同じ値が出現する回数(あるいは区間ごとの頻度)を数え、最も出現頻度が大きいものを取る「最頻値」(mode：モード)がある。

標準偏差は分散の正の平方根で、データが平均値から平均でどのくらい離れているかを表している。算出方法は、各値と平均値の差を二乗した値の和を求め、これをデータの数で割った平均のルートを取る(二乗平均平方根)。

例えば、{10,20,30} という3つの標本の標準偏差は、平均値20を用いて √[{(10-20)²+(20-20)²+(30-20)²}/3] と表され、約8.16となる。{0,20,40} ならば約16.33となり、すべて平均値に等しい {20,20,20} ならば標準偏差は0となる。

分散も散らばり具合を表しているが、元の値と平均の差の二乗の平均であるため、元の値とは次元が異なる。標準偏差はその平方根を取っているため、元の値と同じ次元となり、値自体の大きさと散らばり具合の大きさを同じ尺度で比較することができる。日本では学力試験のいわゆる偏差値を算出するのに用いられている。

統計学の分散

統計学では、あるデータ群のそれぞれの値について平均値との差を取って二乗し、その合計をデータの数で割って平均した値(二乗平均)を分散(variance)という。データ群が平均に対してどのくらい散らばっているかを表す指標として用いられる。

例えば、{10,20,30} という3つの標本の分散は平均値の20を用いて {(10-20)²+(20-20)²+(30-20)²}/3 と表すことができ、約66.7となる。{0,20,40} であれば約266.7となり、すべて平均に等しい {20,20,20} ならば分散は0となる。

分散は算出過程で値を二乗しており元の値とは次元が異なるが、分散の正の二乗根を取って次元を揃えた値を散らばりの指標として用いることがある。これを「標準偏差」(SD：Standard Deviation)と呼び、元の値と同じ尺度で散らばり具合を評価することができる。

分散処理

IT分野では、一つの処理やデータ群に対して複数の機器を動員し、分担して処理する方式を「分散処理」(distributed processing)、「分散システム」(distributed system)、「分散コンピューティング」(distributed computing)などという。

このうち、処理の前後関係に従って異なる機能の機器を連結し、それぞれが特定の工程に専念する方式を「垂直分散システム」、同じ機能の機器を並べて処理を振り分け、並行に処理する方式を「水平分散システム」という。一般には後者を指して単に分散システムと呼ぶことが多い。

2つの事象に関わりがあり、一方が変化するともう一方も変化するような関係を「相関」という。一方が増えるともう一方が増える関係を「正の相関」、一方が増えるともう一方は減る関係を「負の相関」という。

相関係数は同じ数の2つのデータ系列から算出される統計量の一つで、-1から1の間の実数を取る。値が0ならば両者に相関はなく、1なら完全な正の相関、-1なら完全な負の相関がある。1または-1のときは両者の関係を $y=\mathrm{ax}+b$ という形の一次関数として記述することができる。

相関係数は、同数のデータ系列 $(x_1,x_2,\dots ,x_n)$ と $(y_1,y_2,\dots ,y_{\mathrm{n}})$ から算出した共分散 $s_{\mathrm{xy}}$ とそれぞれの標準偏差 $s_x$ および $s_y$ を用いて $\frac{s_{\mathrm{xy}}}{s_x{s}_y}$ として求められる。これは平均 $\stackrel{-}{x}$ と $\stackrel{-}{y}$ を用いて下記の式のように表される。

調査などで得られた様々な数値の組み合わせのうち、着目している数値(従属変数)が、他の数値(説明変数)からどのように影響を受けているかを関数の形で明らかにする。説明変数が一つの場合を「単回帰分析」、複数の場合を「重回帰分析」という。

例えば、ある飲食店のビールの売上(y)とその日の最高気温(x)についての記録を単回帰分析したところ、y=ax+c という1次関数の形で表されたとする。この関係が分かれば、天気予報を元に仕入れ量を調整することができる。降水量(z)との関係も合わせて重回帰分析することで、y=ax+bz+c という関係が明らかになれば、より精度の高い予測が可能となる。

この例では説明変数と従属変数が直線的な比例関係で表されることを仮定しており、これを「線形回帰」あるいは「直線回帰」という。物事の関係性は単純な比例関係で表されるとは限らず、x² のような高次の項を含む多項式、指数関数、対数関数、三角関数などが含まれる場合がある。これを「非線形回帰」という。

統計値などから回帰分析を行う場合、各標本は誤差を含んで一定の範囲にばらついているため、数値計算を繰り返して関数のパラメータ(係数)を推定する。代表的な手法として「最小二乗法」がよく知られ、回帰式から得られる値と各標本の実際の値の誤差を二乗して足し合わせた値が最小になるよう係数を決定する。

調査や測定などで2つの変数の関係について得られたデータを元に、結果と考えられる変数(目的変数)が原因と考えられる変数(説明変数)からどのような影響を受けているかを関数(数式)の形で明らかにする。なお、説明変数が複数ある場合の回帰分析は「重回帰分析」という。

例えば、ある飲食店のビールの売上(y)とその日の最高気温(x)についての記録を単回帰分析したところ、定数a、bを用いて $y=\mathrm{ax}+b$ という1次関数の形で表されたとする。この関係が分かれば、天気予報を元に仕入れ量を調整することができる。

この例では説明変数と目的変数が1次関数で表される直線的な比例関係にあることを仮定しており、これを「線形回帰」あるいは「直線回帰」という。物事の関係性は比例関係で表されるとは限らず、$x^2$ のような高次の項を含む多項式、指数関数、対数関数、三角関数などが含まれる場合がある。このような正比例以外の関係を含む回帰を総称して「非線形回帰」という。

統計値などから単回帰分析を行う場合、各標本は誤差を含んで一定の範囲にばらついているため、数値計算を繰り返して関数のパラメータ(係数)を推定する。代表的な手法として「最小二乗法」がよく知られ、回帰式から得られる値と各標本の実際の値の誤差を二乗して足し合わせた値が最小になるよう係数を決定する。

調査や測定などで3つ以上の変数の関係について得られたデータを元に、結果と考えられる1つの変数(目的変数)が、原因と考えられる複数の変数(説明変数)からどのような影響を受けているかを関数(数式)の形で明らかにする。なお、説明変数が1つの場合の回帰分析は「単回帰分析」という。

例えば、ある飲食店のビールの売上(z)とその日の最高気温(x)、降水量(y)についての記録を重回帰分析したところ、定数a、b、cを用いて $z=\mathrm{ax}+\mathrm{by}+c$ という1次関数の形で表されたとする。この関係が分かれば、天気予報を元に仕入れ量を調整することができる。

この例では説明変数と目的変数が1次関数で表される直線的な比例関係にあることを仮定しており、これを「線形回帰」あるいは「直線回帰」という。物事の関係性は比例関係で表されるとは限らず、$x^2$ のような高次の項を含む多項式、指数関数、対数関数、三角関数などが含まれる場合がある。このような正比例以外の関係を含む回帰を総称して「非線形回帰」という。

通常、複数の説明変数はそれぞれ独立に変動するものが選択されるが、説明変数が多いほど精緻な予測ができると期待される場合などには、互いに強い相関関係を持つ説明変数の組み合わせが採用されてしまう場合もある。そのような状態を「多重共線性」と呼び、データの増減に対して係数が不規則に大きく変化する。

2つの事象に関わりがあり、一方が変化するともう一方も変化するような関係を「相関」という。一方が増えるともう一方が増える関係を「正の相関」、一方が増えるともう一方は減る関係を「負の相関」という。

2つの変数がどの程度比例関係(線形相関)に従って連動しているかを表す係数を「相関係数」(correlation efficient)という。同数のデータ系列 $(x_1,x_2,\dots ,x_n)$ と $(y_1,y_2,\dots ,y_{\mathrm{n}})$ から算出した共分散 $s_{\mathrm{xy}}$ とそれぞれの標準偏差 $s_x$ および $s_y$ を用いて $\frac{s_{\mathrm{xy}}}{s_x{s}_y}$ として求められる。

相関係数は-1から1の間の実数を取り、0ならば両者に線形相関はなく、1なら完全な正の相関、-1なら完全な負の相関がある。絶対的な評価基準はないが、概ね-0.3～0.3程度であれば両者の間に線形の相関はほぼないと判断され、-0.3～-0.6程度であれば弱い負の相関が、0.3～0.6程度であれば弱い正の相関が、-0.6～-1.0程度ならば強い負の相関が、0.6～1.0程度ならば強い正の相関があると判断される。

なお、相関係数は線形(比例)の関係に従っているかどうかを評価する値であるため、比例関係以外の何らかの非線形な関係性に基づいてきれいに連動していても、相関係数は0近辺(線形相関なし)と判定されることになる。両者の関係性は相関係数だけでなく散布図などをよく見て判断すべきとされる。

例えば、様々な科目のテスト結果からデータモデルを作る場合、各科目の得点をそのまま説明変数とすると極めて多次元のモデルになり、分析が困難になる場合がある。このとき、数学の得点Smと物理の得点Spに強い相関があるとすると、係数PmとPpを適当に定めて Smp = PmSm + PpSp と一つの値で代表させてしまうことで、変数の数を減らすことができる。

Smpを第1主成分と呼び、PmとPpは分散を最大化するように算出される。続いて、Smpと直行する組み合わせの中から「国語と英語」のように別の主成分を見つけ出し、第2主成分とする。このプロセスを繰り返して変数の数を削減していく。一つの主成分が3変数以上の合成になることもあり、この例の「数学と物理の総合得点」のような明快な意味付けが難しい組み合わせになることもある。

主成分が含んでいる情報の大きさを「固有値」、その主成分でデータ全体のどのくらいの割合を説明できるかを「寄与率」という。第1主成分から第2、第3…と順に寄与率を累積していった値を「累積寄与率」と呼び、実用上は十分高い累積寄与率(例えば80%)に達したら残りの主成分は無視する。

「冬の気温と桜の開花日」や「親の身長と子の身長」のように、傾向として片方が増えるともう片方も増える、あるいは逆に片方が増えるともう片方は減るといった関係性が見られるとき、両者の間に「相関がある」あるいは、両者は「相関関係にある」という。

一方、片方が原因となってもう一方の変化が引き起こされる関係性を「因果関係」という。相関関係は因果関係を含む概念で、因果があれば必ず相関もあるが、相関があるからといって必ずしも因果もあるとは限らない。

統計学では2つのデータ系列の分布について、一方の値が高ければ高いほどもう一方の値も高くなる(同じ方向に連動する)関係を「正の相関」、一方の値が高ければ高いほどもう一方の値は低くなる(逆方向に連動する)という関係を「負の相関」という。

2つのデータ系列の間にどの程度強い相関が見られるかは「相関係数」という値で表すことができる。これは両者が線形相関(1次関数で書き表せる直線的な関係)にどの程度近いかを表す係数で、「1」ならば完全な正の相関、「0」ならば相関なし、「-1」ならば完全な負の相関があることを表す。

「降水量が増えると川が増水する」といったように、ある事象が別の事象の原因となっているような関係である。「降水量の増大」と「川の増水」の間には「降った雨水が川に流れ込む」という機序が存在する。

一方、2つの事象の変化の間に「一方が変化するともう一方も変化する」という傾向が存在する場合、これを「相関関係」あるいは略して「相関」という。相関は因果を含む概念で、因果関係にある事象間には必ず相関もある。逆に、相関があるからと言って両者に因果があるとは限らない。

例えば、河川敷の湿度と川の水位の変化に相関が見られたとして、「湿度上昇によって水位上昇が引き起こされた」あるいは「水位上昇によって湿度上昇が引き起こされた」とは言えない。両者は共に「降水」という共通の原因の結果に過ぎないからである。このように両方に影響する外部の要因を「交絡因子」という。

二つの事象AとBの傾向に相関が認められる場合、両者に因果関係があり、原因Aによって結果Bが生じている、あるいはその逆であることが疑われる。しかし、AもBの共通する原因X(潜伏変数あるいは交絡因子という)の結果である場合、AとBの間に因果は無い。このような関係を疑似相関という。

例えば、月ごとのリップクリームの売上と火災の発生件数に強い相関が認められたとして、リップクリームが火災の原因になったり、火災がリップクリーム購入の動機になっているのかというと、そうではなく、「季節による湿度の変動」という共通の原因によって両者に同じ傾向の変動が起こっているだけである。

ある事象に関与する要素の間に原因-結果という因果関係が認められるとき、原因を表す変数のことを「説明変数」、結果を表す変数を「目的変数」あるいは「従属変数」という。説明変数を変化させると、これに連動して目的変数も変化するという関係にある。

例えば、バネにおもりを吊るす実験を行うと、バネの伸びの長さ(y)は吊るすおもりの重さ(x)によって説明でき、定数aを用いて $y=\mathrm{ax}$ という一次関数(比例関係)で表されることが分かる。この場合、おもりの重さが説明変数、バネの伸びが目的変数である。

説明変数と目的変数の間の規則性を明らかにすることを「回帰分析」(regression analysis)という。説明変数が一つの場合を「単回帰分析」、複数の場合を「重回帰分析」という。直線的な比例関係を想定して解析することを「線形回帰」あるいは「直線回帰」と呼び、2次関数や指数関数のように直線的でない関係を想定して解析することを「非線形回帰」という。

ある事象に関与する要素の間に原因-結果という因果関係が認められるとき、結果を表す変数のことを「目的変数」、原因を表す変数を「説明変数」あるいは「独立変数」という。説明変数を変化させると、これに追従して目的変数も変化するという関係にある。

例えば、バネにおもりを吊るす実験を行うと、バネの伸びの長さ(y)は吊るすおもりの重さ(x)によって説明でき、定数aを用いて $y=\mathrm{ax}$ という一次関数(比例関係)で表されることが分かる。この場合、おもりの重さが説明変数、バネの伸びが目的変数である。

説明変数と目的変数の間の規則性を明らかにすることを「回帰分析」(regression analysis)という。説明変数が一つの場合を「単回帰分析」、複数の場合を「重回帰分析」という。直線的な比例関係を想定して解析することを「線形回帰」あるいは「直線回帰」と呼び、2次関数や指数関数のように直線的でない関係を想定して解析することを「非線形回帰」という。

尺度水準 (level of measurement)

統計的な変数やその値を、情報の性質に基づいて分類したものを「尺度水準」という。1946年に米心理学者スタンレー・スティーブンズ(Stanley S. Stevens)が提唱した、「名義尺度」「順序尺度」「間隔尺度」「比例尺度」の4段階に分類する考え方が広く普及している。

「名義尺度」(類別尺度)は対象や状態を区別するためだけに(便宜上の)数字を割り当てたもので、値が同じか異なるかしか評価することができない。順序や大きさ、比率などに意味はなく、計算を行うこともできない。例えば、電話番号の国番号は米国が1、日本が81だが、日本が何かの大きさで81位であるとか、何かが米国の81倍であるというわけではない。

「順序尺度」は数字の大小が順序を表すような尺度である。大きさを比較したり順位を付けることができるが、他の値との差や比率には意味がなく、計算を行うことはできない。競技の順位、成績やアンケートなどの5段階評価、検定制度の段位や級などが該当する。「将棋8段は4段より強い」とは言えるが、「2倍強い」といった比較はできない。

「間隔尺度」は数字が順序を表すとともに間隔に意味があるような尺度である。値の差が等しければ同じ間隔が空いていることを意味するが、「0」で表される点は便宜上置いたもので、値の比には意味がない。例えば、摂氏5度が15度になるのと15度が25度になるのは同じ幅だけ温度が上昇したと言えるが、摂氏15度は5度の3倍の温度やエネルギーであるとは言えない。

「比例尺度」(比率尺度)は数字が順序や間隔を表すともに、「0」に原点としての意味があり、値の比や割合も議論することができる尺度である。長さ、重さ、時間、速度、絶対温度などの物理量、金額などが該当する。これらの尺度水準には上下関係があり、名義、順序、間隔、比例の順に水準が高くなる。高い水準の尺度は自身より低い水準の尺度を兼ねている。

統計的な変数やその値を、情報の性質に基づいて分類したものを「尺度水準」という。1946年に米心理学者スタンレー・スティーブンズ(Stanley S. Stevens)が提唱した、「名義尺度」「順序尺度」「間隔尺度」「比例尺度」の4段階に分類する考え方が広く普及している。

名義尺度は最も低い水準の尺度で、数字は対象や状態を識別する名前の役割しか果たさず、量的な意味合いを一切もたない。値が同じか異なるかを見分けるためだけに使用することができ、順序、間隔、大きさ、比率などを表すことはできず、値の計算にも意味がない。統計量としては各値の度数や出現頻度、最頻値などを求めることはできる。

例としては、電話番号や郵便番号、学籍番号、背番号、国際電話の国番号、総務省の都道府県コードなどがある。例えば、都道府県コードで「10」が群馬県、「20」が長野県だが、群馬県が何かで10位であるとか、長野県の何かが群馬県の2倍であるといった意味はない。

統計的な変数やその値を、情報の性質に基づいて分類したものを「尺度水準」という。1946年に米心理学者スタンレー・スティーブンズ(Stanley S. Stevens)が提唱した、「名義尺度」「順序尺度」「間隔尺度」「比例尺度」の4段階に分類する考え方が広く普及している。

順序尺度は名義尺度に次いで2番目に低い水準の尺度で、数字の大小で順序を表すことができる。大きさを比較したり順位を付けることができるが、値同士の差や他の値との比、割合などには意味がなく、値の計算を行うこともできない。統計量としては度数や最頻値に加え、中央値や四分位数、パーセンタイルなどが使用できる。

例としては、競技の順位、成績やアンケートなどの段階評価、検定制度の段位や級、自動車保険の等級、がんのステージ、国際原子力事象評価尺度などが該当する。「将棋8段は4段より強い」とは言えるが、「2倍強い」といった比較はできない。

統計的な変数やその値を、情報の性質に基づいて分類したものを「尺度水準」という。1946年に米心理学者スタンレー・スティーブンズ(Stanley S. Stevens)が提唱した、「名義尺度」「順序尺度」「間隔尺度」「比例尺度」の4段階に分類する考え方が広く普及している。

間隔尺度は比例尺度についで2番目に高い水準の尺度で、数字の間隔が量の大きさを表すような尺度である。値の差が等しければ同じ間隔が空いていることを意味するが、「0」で表される点は量が0になる原点ではなく便宜上置いたものである。値自体の比には意味がないが、値の差同士の比には意味がある。統計量としては最頻値や中央値、パーセンタイルなどに加え、平均値(相加平均)や標準偏差、相関係数なども使うことができる。

例としては、温度の摂氏(℃)や華氏、西暦や元号で表した年、日付などがある。15℃が20℃になるのと20℃が30℃になるのでは2倍の温度上昇が生じたと言うことができるが、15℃が30℃になったのを温度が2倍に上昇したと言うことはできない。

統計的な変数やその値を、情報の性質に基づいて分類したものを「尺度水準」という。1946年に米心理学者スタンレー・スティーブンズ(Stanley S. Stevens)が提唱した、「名義尺度」「順序尺度」「間隔尺度」「比例尺度」の4段階に分類する考え方が広く普及している。

比例尺度は最も高い水準の尺度で、数字がそのまま何らかの量の大きさを表している。値の「0」は「存在しない」ことを表す原点であり、値の間隔や比には意味がある。加減乗除などの計算も行うことができ、すべての統計量を使うことができる。

例としては、長さや面積、体積、重さ、時間、速度、絶対温度などの物理量、金額、個数などが該当する。一段階低い水準の間隔尺度である摂氏では27℃が54℃になったからといって温度が2倍になったとは言えないが、絶対温度600K(約327℃)は300K(約27℃)の2倍の温度と言うことができる。

何らかの主張を統計的な手法で立証したいとき、「その主張は成立していない」という仮説(帰無仮説)を立て、主張の内容はその逆である対立仮説とする。調査や測定、統計量の計算などで帰無仮説が棄却されれば、本来の主張である対立仮説の成立を証明することができる。

このとき、実際には帰無仮説が正しい(主張は成立していなかった)のに、誤って帰無仮説を棄却してしまう過誤を第1種の誤りという。例えば、「新薬に効果がある」という主張のために「新薬には効果がない」という帰無仮説を統計的な検定にかけ、実際には効果がないのに誤って「効果があった」という結論を導いてしまう状況である。

一方、実際には対立仮説が正しい(主張は成立している)のに、誤って帰無仮説を採択してしまう過誤を「第2種の誤り」(第二種過誤)という。先の例では、新薬には実際には効果があったのに、「新薬に効果がない」という帰無仮説が検定を通ってしまい、誤って「効果がない」と結論付けてしまう状況である。

何らかの主張を統計的な手法で立証したいとき、「その主張は成立していない」という仮説(帰無仮説)を立て、主張の内容はその逆である対立仮説とする。調査や測定、統計量の計算などで帰無仮説が棄却されれば、本来の主張である対立仮説の成立を証明することができる。

このとき、実際には帰無仮説が誤っている(主張は成立している)のに、誤って帰無仮説を採択してしまう過誤を第2種の誤りという。例えば、「新薬に効果がある」という主張のために「新薬には効果がない」という帰無仮説を統計的な検定にかけ、実際には効果があるのに誤って「効果がない」という結論を導いてしまう状況である。

一方、実際には帰無仮説が正しい(主張は成立していない)のに、誤って帰無仮説を棄却してしまう過誤を「第2種の誤り」(第二種過誤)という。先の例では、新薬には効果がなかったのに、「新薬に効果がない」という帰無仮説を検定によって棄却してしまい、誤って「効果がある」と結論付けてしまう状況である。

単一のデータを表すデータ型の総称で、スカラの一つの変数にはその型の値を一つだけ格納することができる。多くの言語では整数型、浮動小数点数型、ブール型、文字列型などのスカラが用意されている。

一方、複数のスカラのデータを組み合わせて一つのデータ構造を定義したものを「複合データ型」(composite data types)、複数の同じスカラのデータを一定の構造や規則に従って並べたデータ集合を「コレクション」(collection)という。

同じデータの種類でも言語によってスカラだったり複合的なデータ構造だったりすることがある。例えば、現代の多くの言語では文字列は文字列型(「string」などの型名で表される)というスカラの一種だが、C言語などでは文字列を文字型(char型)の配列として表す。

「ベクトル」表記はドイツ語の “Vektor” に由来し、古くからこの概念を用いている数学や物理学で多く見られる。「ベクター」あるいは「ベクタ」表記は英語の “vector” に由来し、IT分野などで多く見られる。

可変長配列

プログラミングなどの分野では、1次元の配列変数として表現できる、同じ型のデータを一列に並べたデータ構造のことをベクトルと呼ぶ場合がある。これと対比して、単体の値や変数のことは数学の用語にならって「スカラ」(scalar)と呼ぶ場合がある。C++言語やJavaなどでは、要素数を後から増減できる可変長配列を扱うことができるクラスのことをベクトル(vector/Vector)という。

ベクトル演算

並列処理の一種で、一列に並んだ一定の数の複数の値に対して同時に同じ演算を行うことを「SIMD」(Single Instruction Multiple Data)あるいは「ベクトル演算」という。

このような処理に適した論理回路を実装したマイクロプロセッサ(CPU/MPU)を「ベクトル型プロセッサ」、そのようなプロセッサで構成されたコンピュータを「ベクトル型コンピュータ」(ベクトル計算機)という。

かつてはスーパーコンピュータの高速化手法として期待されたが、適用場面が限られプログラミング手法が特殊なことからあまり普及しなかった。現在ではGPU(Graphics Processing Unit)が3次元グラフィックス処理の高速化を行う手法として特定の演算のみをベクトル的に処理する方式が広まっている。

ベクタ画像

画像処理の分野で、画像を点の座標とそれを結ぶ線や面の方程式のパラメータ、および、塗りつぶしや特殊効果などの描画情報の集合として表現する方式を「ベクトル画像」(vector image)、「ベクトルグラフィックス」(vector graphics)などという。

対義語は「ビットマップ」(bitmap)あるいは「ラスタ」(raster)で、これは画像を色のついた点(ピクセル、ドット)を縦横に規則正しく敷き詰めて画像を表現する形式である。

同じ数を何度も掛ける冪乗の計算で、掛ける回数に相当する数を「指数」(exponent)というが、掛ける数と掛けた結果の数が分かっているときに、指数がいくつになるかを表したものが対数である。

例えば、2の3乗は $2\times 2\times 2$ で8($2^3=8$)となるが、2と8が分かっているとき、2を8にするための指数3を「2を底とする8の対数」と表現し、「${\log }_{2}8=3$」のように表記する。8のことを「真数しんすう」と呼ぶことがある。底は1以外の正の値で、真数は正の数である必要がある。冪乗計算では $b^x{b}^y=b^{x+y}$ となるため、対数計算でも ${\log }_b\mathrm{XY}={\log }_{b}X+{\log }_{b}Y$ が成り立つ。

数学では底を10とする「常用対数」(common logarithm)を用いることが多く、底を省略して「$\log x$」のように表記することが多い。また、ネイピア数 $e$ を底とする対数を「自然対数」(natural logarithm)と呼び、「$\ln x$」のように表記する。コンピュータ科学では2進数を多用する関係で2を底とした対数(binary logarithm)を用いることが多く、底を省略したら2とみなす慣習がある。

方程式f(x)=0に対して関数y=f(x)を考え、まず適当なxを取ってf(x)に対する接線を求める。接線がx軸の交点におけるxの値は最初のxよりも解に近いため、このxについて再び接線を求めると、そのx軸との交点はさらに解に近づく。この操作を何度も繰り返し行なっていくと、xの値は解に収束していくため、適当な回数で操作を打ち切ることにより、回数に応じた精度の解の近似値を得ることができる。

非線形方程式を数値的に求める手法として古くから広く知られており、二分法より収束が早く、少ない計算回数で効率よく近似解の精度を高められる。1669年に万有引力の法則などで知られるアイザック・ニュートン(Isaac Newton)が考案し、1690年にジョセフ・ラプソン(Joseph Raphson)によって改良された。二人の名を取ってニュートン・ラプソン法(Newton-Raphson’s method)と呼ばれることもある。

循環小数や無理数、長い桁の小数などを計算する場合に、浮動小数点型や整数型の数値として表すため、これらのデータ型で表現可能な桁数より後ろの値を切り上げや切り捨て、四捨五入などによって捨て去ることがある。このような下位桁を削る処理を「丸める」(丸め処理)と呼び、このとき捨てた値によって本来の値との間に生じるズレを丸め誤差という。

コンピュータは数値を2進法を用いて限られた桁数で表現するため、丸め誤差は整数と実数の間だけでなく、仮数部の桁数の異なる浮動小数点型(float型とdouble型など)の間や、十進数では有限桁の小数値を2進数で表現しようとすると循環小数になってしまう場合(十進数の0.1を2進数で表すと0.00011001100110011…となる)などでも生じることがある。

丸め誤差は取り扱える桁数の制約から仕方なく生じるため、完全に回避することは困難だが、数値の表現形式や計算手順を工夫して影響を小さく抑えることは可能な場合もある。

無限小数や無限級数、数値積分、極限値などの計算をコンピュータで行う場合、無限回の計算を行うわけにはいかないため、ある項までで計算を切り上げ、以降の項の値は計算結果は反映されなくなる。これによって正しい結果との間に生じる差を打切り誤差という。

一回の値の算出における打切り誤差が小さくても、コンピュータシミュレーションなどで大規模に計算を繰り返す場合は誤差が蓄積されて最終的な結果の精度に影響する場合もある。原理上完全に避けることはできないが、計算に用いる級数をより収束の速いものに変形したり、より正確な近似法を用いるなどの手法により切り捨てられる値を小さくして打切り誤差を緩和できる場合がある。

待ち行列は先頭が常に最も古い要素になるデータ構造で、新しい要素は必ず末尾に追加される。取り出すときは常に先頭の最も古い要素から取り出される。このように先に入れたものほど先に取り出される管理方式を「FIFO」(First-In First-Out：先入れ先出し)という。

実装上は、待ち行列のために確保された記憶領域の中ですべての要素が到着順に並ぶとは限らず、実際の位置や順序とは別に到着順や末尾の位置などの情報を内部的に記録・管理する手法が用いられることが多い。人間の行列のように要素が取り出されるたびに残りのすべての要素の物理的な位置を隣(一つ前)に移動させるのは非効率だからである。

バリエーションとして、列の両端から要素の追加や取り出しを行える「両端キュー」(double-ended queue)や、追加する要素に優先度を設定して、優先度の高いものから取り出すようにする「優先度付きキュー」(priority queue)などがある。

一方、「先に足された要素ほど後に取り出される」(末尾から順に取り出す)という規則で要素の出し入れを管理するデータ構造は「スタック」(stack)と呼ばれる。そのような管理方式を「LIFO」(Last-In First-Out：後入れ先出し)あるいは「FILO」(First-In Last-Out：先入れ後出し)という。

要素の出し入れ

待ち行列に要素を追加する操作を「エンキュー」(enqueue)、取り出す操作を「デキュー」(dequeue)という。エンキューされた要素は待ち行列の末尾に追加され、キューの要素数は1増加する。

デキューを指示すると待ち行列の先頭の要素が取り出され、その要素はキューから取り除かれる。先頭から2番目にあった要素(2番目に古かったデータ)が新しい先頭になり、キューの要素数は1減少する。

キューイング (queuing/queueing)

待ち行列を用いて要素の管理を行うことを「キューイング」(queuing)という。キューイングは機器間やプログラム間など独立に動作する二つの主体の間で非同期にデータの受け渡しを行う手法としてよく用いられる。システム間で汎用的にデータを受け渡しするシステムを「メッセージキュー」(message queue)という。

例えば、コンピュータからプリンタにデータを伝送する速度とプリンタがデータを紙に印刷する速度では、後者のほうが圧倒的に遅い。伝送と印刷を同時に行おうとするとコンピュータ側はほとんどの時間待たされることになり無駄であるため、印刷データを一旦待ち行列に保管し、プリンタの処理の進み具合に応じて専用の制御プログラムが少しずつデータを伝送する手法が用いられる。

M/M/1モデルでは「窓口に人がやってくる時間間隔はポアソン分布に従ってランダムである」「各々が窓口で用を足す時間の長さは指数分布に従ってランダムである」「窓口の数は一つ」の3つの条件を満たす待ち行列について分析する。

単位時間あたりに窓口に来る人数を処理できる人数で割ったものを利用率という。M/M/1モデルにおける平均の待ち時間は利用率を用いて、利用率/(1-利用率)×平均サービス時間 という式で表されることが知られている。

M/M/1モデルはレジや券売機、ATMに利用者が並んでいる様子を表す数学的なモデルとしてよく知られるが、ITの分野でも、一台のサーバに次々にクライアントが要求を送信し、サーバがこれを処理して応答するといったシステムの挙動を分析するのに有用である。

「M/M/1」の表記は「ケンドールの記号」と呼ばれる表記法の一つで、待ち行列の特徴を表している。先頭から順に、到着の過程、処理時間の分布、窓口の数を表した略号である。到着がポアソン分布に従うマルコフ過程、処理時間は指数分布に従うマルコフ過程であるため、いずれも “Memoryless” (無記憶)あるいは “Markovian” の頭文字を取って「M」となる。窓口は一つのため「1」で、順に繋げると「M/M/1」となる。

例えば、関数 ƒ(x) = x²-2x+3 について x>0 における最小値を求める、といったように定式化できる問題を指す。このとき、対象となる関数を「目的関数」、変数について課される条件を「制約条件」あるいは「制約関数」という。

この例では x=1 のとき ƒ(x)=2 となり最小となる。ƒ(x)=2 をこの問題における最適値と呼び、これを与える x=1 を最適解という。最大を求める問題と最小を求める問題を区別して、最大値および最大解、最小値および最小解と呼び分ける場合もある。

変数が連続的に変化するような関数の最適値を求める問題は「連続最適化問題」と呼ばれ、目的関数が一次式で表される線形計画問題などが含まれる。一方、変数が離散的な値しか取らないような問題は「離散最適化問題」あるいは「組み合わせ最適化問題」と呼ばれ、情報科学の有名な問題である最短経路問題、ナップサック問題、巡回セールスマン問題、エイトクイーン問題などはこちらに含まれる。

複数の変数の関係について、不等式で表される制約条件が複数与えられ、等式で与えられる目的関数があるとき、目的関数の値が最大あるいは最小となるような変数の値の組み合わせを求める。

制約条件は、例えば「x+2y<12」「2x+y<12」といった形で一次不等式の形で与えられ、目的関数は「x+y」のようにやはり一次式として表される。この例の場合、制約条件を満たすxとyの値の組み合わせの中で「x=4,y=4」という組み合わせの場合に目的関数の値が最大値である8を取る。

解が存在するような問題設定の場合、2変数ならば制約条件を満たす値が含まれる領域を平面に図示すると多角形(多変数の場合は凸多面体)となり、そのうちの頂点のいずれかが解となる。多変数や多条件の場合に効率良く解を探索する計算手順(アルゴリズム)にはシンプレックス法や内点法などがある。

線形計画法のうち、解を整数に限定したものを「整数計画法」という。条件や目的関数に線形(一次式)ではないものを含む手法は「非線形計画法」(NLP：Non-Linear Programming)という。現実世界では様々な制約の下で最大の効用を得る問題は多くあり、生産や輸送、人員配置の計画などに広く応用されている。

PERTでは各工程を「前の工程が終わらないと次の工程が始められない」という依存関係に従って矢印で繋いでいき、それぞれの工程には所要時間を記入していく。

出来上がったネットワーク図(アローダイアグラム、PERT図とも呼ばれる)にはプロジェクト開始から終了まで通常いくつかの経路が現れる。経路をたどって各工程の所要時間を足し合わせていくとその経路の所要時間が求められ、その中で最大のものがプロジェクト全体の工期の見積りとなる。

クリティカルパス

所要時間が最大となる経路に存在する工程はどれか一つでも遅れると全体が遅延するため、重要な工程のみが集まった「クリティカルパス」(critical path)と呼ばれる。

全体の工期を短縮するにはクリティカルパスを短縮しなければならないため、スケジュールや人員配置の変更、資源の集中投下などの判断を行うことが必要となる。

その際、ある工程の所要時間が変化すると、これまでとは別の経路がクリティカルパスになる場合があるため、PERT図の作成と分析はプロジェクト進行中に何度も繰り返し行なうことが重要となる。

対義語は「デジタル」(digital)で、情報を離散的な数値に変換し、段階的な物理量として表現する。アナログで情報を扱う利点として、デジタル化では避けられない離散化に伴なう本来の信号からのズレ(量子化誤差)が生じないという点があり、情報の発生時点では正確に表現して記録することができる。

一方、保存や伝送、再生、複製に際して劣化やノイズによる影響を受けやすく、変化した情報は復元することができないため、伝送・複製を繰り返したり長年に渡って保存すると内容が失われたり変質してしまう難点がある。

かつて音楽の販売に用いられたレコード盤は、樹脂表面に刻まれた溝の凹凸の変化が音声信号の変化に直接対応付けられたアナログ記録方式だったが、コンパクトディスク(CD)では音声信号をサンプリング(標本化)して離散的な数値の列に変換し、これを表面の溝の凹凸にデジタル信号として記録している。

機器などの内部的にはデジタル処理が行われていても、人間には連続的に感じられる多段階の値で量を識別するような方式を便宜上アナログと呼ぶ場合がある。例えば、ゲーム機のコントローラの種類の一つで、方向の指示を多段階に滑らかに変化させられるものをアナログコントローラという。

1990年代頃までは、コンピュータなどによる情報のデジタル処理は限られた用途にのみ用いられてきたが、半導体チップやデジタル機器の性能向上や低価格化により、現代では身近な情報の多くがデジタル方式で保存、加工、伝送されるようになってきている。

比喩や誤用

コンピュータやデジタル方式の情報機器、通信サービスなどが普及するに連れ、旧来の機器や仕組み、考え方などを比喩的にアナログと称するようになった。

そのような用例の多くは情報の表現形式のデジタル・アナログとは無関係で、単に「コンピュータやインターネットによらない」という意味だったり、さらには「電気機械を使わない」ことを表していたりする。

中には本来の語義では誤用と思われる用例もある。例えば、ビデオゲームと対比してカードゲームやボードゲームを「アナログゲーム」と呼んだり、パソコンや電卓と対比してそろばんを「アナログな計算方法」と評することがあるが、これらが扱う情報は離散的な数値であり、電気機械を使っていないだけで情報の取り扱い方自体はデジタル的である。

現代のコンピュータはデータをすべて2進数の値の列に置き換え、これをスイッチのオン・オフや電圧の高低など明確に区別できる2状態の物理量に対応させて保存・伝送する。これに合わせて、通信回線や記憶媒体などもデジタル方式で情報を取り扱うようになっている。

対義語は「アナログ」(analog)で、情報を連続した物理量で表現する方式を意味する。初期の情報機器はアナログテレビ放送や音楽レコードのようにアナログ方式で情報を記録・伝送していたが、現代ではコンピュータの普及に合わせて動画配信やCDのようにデジタル方式への置き換えが進んでいる。

デジタルで情報を扱う利点として、保存や伝送、再生、複製などを行う際に劣化やノイズの影響を受けにくく、伝送・複製を何度繰り返しても内容が変化しない点や、様々な種類の情報を数値の集合として同じように扱うことができ、情報の種類によって媒体の選択に制限を受けない点などがある。ただし、連続的に変化する信号を離散値に変換する際に、必ず本来の信号からのズレ(量子化誤差/標本化誤差)が生じる。

機器などの内部的にはデジタル処理が行われていても、人間には連続的に感じられる多段階の値で量を識別するような方式を便宜上アナログと呼ぶ場合がある。例えば、ゲーム機のコントローラの種類の一つで、方向の指示を多段階に滑らかに変化させられるものをアナログコントローラという。

比喩や誤用

コンピュータやデータ通信、デジタル方式の記憶媒体などが普及するに連れ、「デジタル」という語をコンピュータやインターネットに関連するものの総称、「アナログ」をその逆、すなわち「電気・電子技術に依らないもの」とする比喩的な用法が広まった。

このような用例の多くは本来の情報の表現形式の違いとは無関係に用いられるため、カードゲームやボードゲームなどをビデオゲームに対比して「アナログゲーム」と呼んだり、そろばんを計算機と対比して「アナログな計算方法」と呼んだりするが、これらは離散的な数値しか扱わないため、情報の扱い方そのものはデジタル的である。

音や光、電気、電波など物理現象に伴う信号は本来連続量であるため、そのままではコンピュータなどの電子回路で取り扱うことができない。そこで、一定の決まった間隔で信号の強度を測定(標本化/サンプリング)し、決まった細かさの段階に当てはめて表していく。

例えば、4段階の値で量子化を行う系では、信号強度の測定値(標本)は0、1/3、2/3、1の中から最も近い値が選ばれる。0.1に近い標本は0、0.4に近い標本は1/3といった具合である。この段階の数が多いほど元の信号をより高い精度で忠実に表現することができるが、量子化後のデータ量はその分だけ増大する。

この細かさをビット数で表したものを「量子化ビット数」と呼び、これが1ビットであれば2段階(2¹)、8ビットならば256段階(2⁸)、16ビットならば65,536段階(2¹⁶)の細かさで強度を表現できる。

アナログ信号のサンプリング

信号処理の手法の一つで、アナログ信号などの連続量の強度を一定の時間間隔で測定し、観測された値(標本値)の列として離散的に記録することを標本化ということが多い。デジタルデータとして記録したい場合は、値を整数などの離散値で表す「量子化」(quantization)処理が連続して行われる。

測定の間隔を「標本化周期」(sampling cycle：標本化周期)、その逆数である測定の頻度(単位時間あたりの回数)を「標本化周波数」(sampling frequency：標本化周波数)という。頻度の多寡は通常標本化周波数で表現され、単位として1秒あたりの回数を表す「Hz」(ヘルツ)が用いられる。

例えば、音声を44.1kHz(キロヘルツ：Hzの1000倍)で標本化する場合、音声信号の強度を毎秒4万4100回記録し、音声データを1秒あたり4万4100個の数値の列として表現する。44.1kHzは人間の可聴音をほぼカバーする周波数とされ、CD(コンパクトディスク)などの音声記録に用いられている。

統計・調査におけるサンプリング

統計や調査などの分野では、調査したい母集団全体を対象とすることが困難な場合に、集団を代表する少数の標本を抽出して対象とし、その結果から統計的に母集団の性質を推計する手法を標本化という。製品の出荷時検査や社会調査などで広く用いられ、標本から母集団の推定値を算出する方法や偏りのない標本の抽出方法などについて様々な手法が提唱されている。

音楽におけるサンプリング

音楽の分野では、楽曲の制作手法の一つで、既存の楽曲や何らかの音源からメロディや歌詞、あるいは音声そのものの断片を抽出し、引用したり繋ぎ合わせる技法を標本化という。また、録音した楽器の音や環境音、人や動物の声などを短い単位に分解し、再構成して楽曲に仕上げる手法のことを標本化ということもある。

単位時間あたりの標本化の回数をサンプリング周波数(サンプリングレート)と呼び、毎回の標本データを表現する値のビット数を量子化ビット数という。これらの値が大きいほどアナログ波形をより正確にデジタルデータの集合として記録できるが、単位時間あたりの記録に必要なデータ量は増大する。

音声や光(画像・映像)、電気信号、電波などを電子機器に取り込んでデジタル処理するためには、センサーやアンテナなどが得たアナログ信号をA/D変換でデジタルデータに変換する必要があり、様々な機器の内部に内蔵されている。

A/D変換とは逆に、デジタル信号を元にアナログ信号を生成する電子回路のことをDAC(D/Aコンバータ、デジタルアナログ変換器)という。

ある形式のアナログ信号やデジタルデータを特定の形式の符号(code)に置き換える操作を指す。得られた符号列に逆方向の変換を行って元の状態に戻す操作は「デコード」(decode)という。デコードによって符号化前の状態を復元することができるが、非可逆圧縮など完全に元の状態には戻せない方式もある。

例えば、動画データは極めてデータ量が大きいため、符号化処理によってデータの間引きや圧縮を行い、短い符号列に置き換えてから保存や伝送を行う。圧縮されたデータはそのままでは再生できないため、再生時にはデコード処理によって元のデータを取り出してから表示を行う。

ある方式の符号化処理を行う装置やソフトウェアを「エンコーダ」(encoder)、その方式でデコード処理を行うものを「デコーダ」(decoder)という。音声の録音と再生、映像の録画と再生など、状況に応じてどちらも行う可能性がある場合には、両者を一体化した「コーデック」(codec：encoder-decoder)を用いる。

1952年にデビット・ハフマン(David Albert Huffman)氏が考案した。符号化方式を「ハフマン符号化」(Huffman coding)、得られる圧縮符号を「ハフマン符号」(Huffman code)という。圧縮符号を展開すると完全に元通りのデータを復元することができる可逆圧縮の代表例で、現代でもファイル圧縮や画像ファイル形式など様々な場面で応用されている。

基本的な考え方は、対象データ列に出現する各パターンの頻度を調べ、高頻度で現れるパターンには短い符号(ビット列)を、低頻度のパターンには長い符号を割り当てることで全体のデータ長を短縮する。このような圧縮符号を「エントロピー符号」という。

ハフマン符号ではデータ全体を一定の長さの断片ごとに区切り、同じパターンの断片の出現回数を数え上げる。最も頻出するものから順に短い符号を割り当て、パターンを符号に置き換える。置換後の符号列中で各符号を一意に識別できるようにするため、「ハフマン木」と呼ばれる二分木でパターンと符号の対応関係を管理する。

符号化のためにはパターンの出現頻度を調べる必要があるが、最初に出現頻度をすべて調べて符号の割り当てを決めてから符号化を行う方式(データ全体を2回走査する)を「静的ハフマン符号」(static Huffman coding)、出現頻度を調べ符号の割り当てを変更しながら同時に符号化を進めていく方式(一度の走査で済む)を「適応的ハフマン符号」(adaptive Huffman coding)という。

実装が難しく、かつては特許で保護されていた「算術符号」(arithmetic coding)を除けば、理論上最も圧縮率が高いエントロピー符号化アルゴリズムとして知られる。実装も比較的容易であることから、Zip(Deflate)やJPEG、MP3など様々な圧縮形式の仕様の一部に採用され、広く普及している。

同じ情報を短いデータ長で表現することで、記憶装置上で占有する領域を小さくすることができ、また、機器間をより短い時間や少ない回線の占有度で伝送することができる。ただし、圧縮後の符号列は元のデータを扱う処理系では利用できないため、使用前に必ず元の状態に戻す処理が必要となる。この復元処理は「解凍」「伸長」「展開」などと呼ばれる。

圧縮処理や解凍処理に費やされる計算量や計算時間などと引き換えにデータ量の縮減という成果を得ており、両者が見合わなければ圧縮を行う意義は失われる。例えば、データ伝送を高速化するためにデータ圧縮を導入したのに、圧縮、伝送、解凍の合計時間が元データの伝送時間を上回ってしまっては元も子もない。

圧縮の逆変換の呼称

圧縮(compress)後の符号列から元のデータを復元する逆方向の変換処理のことを英語では “decompress” (compressに否定の接頭辞de-を付したもの)というが、日本語では定まった訳がなく、解凍、伸長、展開などの用語が用いられる。

ファイルのアーカイバでは複数のファイルを一つの圧縮ファイルにまとめることが多いため、その中から指定されたものを取り出して元の状態に戻すことを「抽出」ということもある(英語でもこの文脈では “extract” を用いる)。

日本では1980年代にパソコン通信やファイル圧縮ソフトの付属文書などを通じて「解凍」という用語が広まった(対応して圧縮のことを凍結と呼ぶこともあったがこれは広まらなかった)ため、慣用的に解凍と呼ぶことが多いが、本来の語義として圧縮と解凍では意味が対応しておらず、解凍には容積の増減の意味はないことなどから批判も多い。

一方、伸長や展開は、伸ばす、広げるという意味は合っているが、圧縮の逆の動作としての元に戻すという意味合いは薄いとの批判もあり、あまり定着していない。

圧縮率と圧縮比

どのくらい圧縮できたかを圧縮率という用語で表すことがある。より小さい量に圧縮できたことを「圧縮率が高い」という。

実際には二つの異なる指標が圧縮率と呼ばれており、一つは圧縮後のデータ量の元のデータ量に対する比率、もう一つは削減量の元の量に対する比率である。いずれを指すのかは文脈により異なる。圧縮後にデータ量が元の10分の1になったことを、前者の指標では圧縮率10%、後者では90%と表現する。

一方、圧縮前と後のデータ量の比や倍率で圧縮の程度を表すこともあり、データ圧縮比と呼ばれる。10分の1に圧縮したことを10:1あるいは10倍と言い表す。

可逆圧縮と非可逆圧縮

完全に元のデータに戻せる符号列に変換する方式を「可逆圧縮」、元のデータの一部を削除・変形することで高い圧縮率を得る代わりに完全には元に戻せなくなる方式を「非可逆圧縮」あるいは「不可逆圧縮」という。

可逆圧縮はわずかでもデータの一部が異なれば元とはまったく違う意味になってしまう文字(テキスト)データやコンピュータプログラムの圧縮や汎用のファイル圧縮などで用いられ、通常単にデータ圧縮といえば可逆圧縮を指す。

非可逆圧縮は主に画像や音声、映像など元のデータに大きな情報の冗長性が含まれる対象に用いられる。人間の視覚や聴覚の特性を利用して、人間が気づきにくい形でデータの一部を改変・削除することで、劇的な高圧縮率を得ることができる。

元の情報を損なう変換を伴うため、非可逆圧縮は厳密にはデータ圧縮手法の一部ではないとする立場もある。また、非可逆圧縮アルゴリズムの中には、元データの形式変換や加工(この段階ではデータ長の縮減は伴わない)を行った後、データ圧縮自体は連長圧縮などの可逆圧縮により行う(すなわち、「非可逆」の工程では圧縮していない)ものも多い。

コンピュータはすべての情報を「0」と「1」のを組み合わせたデジタルデータとして取り扱う。数値は2進数を用いることで容易に表現できるが、文字は字形そのものを画像や図形としてデータ化したものはデータ量が多く、これをそのまま繰り返し並べて文字データとすることは無駄が大きい。このため、各文字に短い識別番号(正確には0と1の並び：ビット列)を与えて数字の列として文字列を表現するようになった。この数字と文字の対応関係を定めた規約が文字コードである。

最も普及しているASCII文字コードは英数字や制御文字、記号などを収録した7ビット(7桁のビット列、十進数では0～127)のコード体系であり、例えばアルファベットの大文字の「A」は65番(ビット列で1000001)、小文字の「z」は122番(同1111010)などと定められている。あるデータ列がASCII文字列であることが分かっていれば、番号との対応関係を元に文字の並びを知ることができる。

文字集合と符号化方式

文字コードを定義するには、どの言語を対象にどの文字を収録するかを決めなければならず、まず収録する文字(の字形)を特定して列挙した文字集合(文字セット)を定める。その際、番号などは与えずにただ収録する文字群を定義したものをレパートリ、各文字に一意の番号を与えたものを符号化文字集合(CCS：Coded Character Set)という。

欧米圏の8ビット文字コード規格のように、符号化文字集合をそのまま文字コードとして利用することも多いが、漢字圏など収録文字数の多い言語では各文字に割り当てられた符号をどのようなビット列で表現するかについて、いくつかの異なる方式を定めている場合があり、これを文字符号化方式(CES：Character Encoding Scheme/文字エンコーディング)という。

例えば、代表的な日本語の符号化文字集合の一つであるJIS X 0208規格に定められた符号をそのまま文字コードとしたものを区点コードというが、この文字集合を対象とする符号化方式としてJISコードやShift JISコード、日本語EUC(EUC-JP)などが定められており、同じ文字でも符号化方式によってそれぞれ異なったビット列で表現される。世界中の文字を収録したUnicodeでも、同じ文字集合に対してUTF-8、UTF-16、UTF-32など複数の異なる符号化方式が定義されている。

10進数の1桁の数字を1バイト(8ビット)で表す。前半4ビットは文字コードの種類表す「ゾーン部」と呼ばれるデータで、EBCDICコードなら「1111」(15)、JISコードなら「0011」(3)が設定される。

後半4ビットは1桁の数字(0～9)を4桁の2進数(4ビットのバイナリデータ)に対応させ、「0000」(0)から「1001」(9)までのビットパターンで置き換える。末尾の4ビットは正負の符号を表すコードで、通常は正を「1100」(12)、負を「1101」(13)とするが、一部の機種や処理系では異なる値が用いられることもある。

主に英語で必要な文字を収録したコード規格で、0番から127番までの番号(正確には2進数で0000000から1111111まで)について、各番号がどの文字を意味するかという対応関係を定めている。例えば英大文字の「A」はASCIIコードコードでは65番(16進数で41、2進数で1000001)で表される。

収録されているのはA～Z、a～zのラテンアルファベット(ローマ字)、0～9のアラビア数字、約物(引用符や括弧、疑問符、感嘆符、カンマ、ピリオドなど)、記号(数学記号やドルマーク、アットマークなど)、空白文字、制御文字(改行文字やタブ文字、古い通信制御文字など)などである。

1963年にASA(アメリカ規格協会、現在のANSI)が定めた規格で、1967年に国際標準化機構(ISO)がほぼ同じ内容をISO/IEC 646として標準化した。1970年代以降ほとんどのコンピュータやソフトウェアが標準の文字コードの一つとして対応しており、英文の文字情報の記述やコンピュータ言語の表記などに用いられている。一般的なキーボードにはASCIIコード文字に対応するキーが配されている。

8ビット目を利用した拡張規格

ASCIIコードでは1文字を7ビットで表すが、現代のコンピュータのほとんどはデータの基本的な管理単位が1バイト(8ビット)であるため、実際には1文字を8ビットで表している。

残りの1ビットはもともとデータ伝送時の誤り検出符号(パリティビット)などとして用いられてきたが、電子回路や通信システムの信頼性向上などを受け、この1ビットを活用してASCIIコードを拡張する試みが行われるようになった。

ASCIIコードを拡張したコード体系では、0から127まではASCIIコードと同じで、ASCIIコードに規定の無い128～255の領域に独自の文字を割り当てている。例えば、日本国内で用いられたJIS X 0201では、この領域にカタカナ(いわゆる半角カナ)や句読点(。、)、鉤括弧(「」)を配置して限定的ながら日本語を使えるようにしている。

後にASCIIコード拡張についても標準化の動きが起こり、8ビットコードや複数バイトコードの扱い、各国の拡張コードの切り替え方式などを定めたISO/IEC 2022や、これに基づいて具体的な8ビットの文字コードを規定したISO/IEC 8859などの規格が策定された。追加の文字を含めても1バイトで十分なヨーロッパ各国の言語などではISO/IEC 8859が標準的な文字コードとして普及している。

初期のEUC

1970年代後半にこの用語が使われだした頃のコンピュータは操作に専門的な技術を要する大型コンピュータで、業務部門の利用者は電算部門の専門の技術者やオペレータに端末の操作やデータの入出力の依頼をしてシステムを利用していた。

当時のEUCのコンセプトは、コンピュータに扱いやすい表示・操作システムを実装し、データ処理を必要とする利用者自身が端末を操作して様々な処理を実行するというもので、経営者や上級管理職向けのDSS(意思決定支援システム)などの形で結実した。

現在のEUC

1990年代後半頃になるとオフィスで一人一台パソコンが与えられ、従業員が自分で操作するのが次第に当たり前になっていき、通常のシステムの使用に関しては技術部門の仲介は不要になった。当初の意味でのEUCは浸透したと言える。

この頃からEUCの指す意味は徐々に変容していき、情報部門の用意したソフトウェアやパッケージ製品をそのまま利用するのに留まらず、業務に必要な個別のアプリケーションなどを利用者が自ら開発・運用することを指すようになっていった。

業務に必要なITシステムをゼロから構築することという極端な事例は少なく、パッケージソフトのマクロ機能(Excelマクロ等)やスクリプト機能(VBA等)などを利用して簡易な自動処理プログラムを開発したり、最新のIT機器を部署内で独自に導入して既存システムに接続するといった事例が多い。近年では既存システムの定型的・反復的な作業を自動化するRPA(Robotics Process Automation)が注目されている。

この意味でのEUCが無秩序に行われるとIT部門や管理部門の統制が及ばず、思わぬトラブルや多重投資などの問題を引き起こす(シャドーIT問題)ことがあるため、ガイドラインを定めるなど一定のルールのもとで実施する必要がある。

文字コード規格で各文字に付けられた番号を一定の規則で符号化する方式を定めたもので、「エスケープシーケンス」(escape sequence)という特殊な制御文字を挿入することにより複数の文字集合(いわゆる半角文字と全角文字など)の切り替えを行う。同じコードでも直前のエスケープシーケンス次第で別の文字を指し示すことがあるため、文字列は先頭から順に読み込まなければならないという制約がある。

ASCII文字コードで定義された制御文字やラテン文字(いわゆる半角英数字・記号)に加え、JIS X 0208で定義された日本語文字(ひらがな、カタカナ、漢字)やギリシャ文字、キリル文字、全角記号などを記述できる。いわゆる半角カタカナは含まれていない。

最初の仕様は1993年にRFC 1468として標準化され、1997年にはJIS X 0208の改訂版に収録され国内の公的な標準規格となった。その後、JIS X 0212で定義された文字を扱えるようにしたISO-2022-JP-1(RFC 2237)などいくつかのバリエーションが策定された。

Unicodeの普及以前に、Shift JISコード、日本語EUCコード(EUC-JP)と並んで古くからよく用いられてきた有力な日本語文字コードの一つである。特に、1990年代後半のインターネットの一般への普及の初期に、8ビット単位の文字コードが欧米で開発された電子メールソフトウェアなどと相性が悪かった(7ビットコードしか想定していないものが多かった)ことなどから、電子メールで日本語を扱う際の事実上の標準として広まった。

コンピュータで文字データを扱うには、文字や記号の一つ一つに対応する番号(符号)を与え、文字の列を番号の列に変換する必要がある。文字と番号の対応関係を定めた仕様を「符号化文字集合」、番号を具体的なビット列として表す変換ルールを「文字エンコーディング」という。

シフトJISコードは「JIS X 0201」や「JIS X 0208」などの標準規格で定められた符号化文字集合を対象とする文字エンコーディング仕様の一つで、JIS X 0201の半角英数字や制御文字、半角カタカナを1バイトで、JIS X 0208の全角文字を2バイトで表すことができる。

主な特徴

JIS漢字コードを対象としたエンコーディング方式には、いわゆる「JISコード」の通称で知られる「ISO-2022-JP」や、UNIX系OS向けに策定された「EUC-JP」(日本語EUC)もある。これらが連続したコード領域で文字を表すのに対し、シフトJISコードでは文字集合をいくつかに分割し、それぞれ異なる離れた領域へ移動(shift)させている。

これは、2バイト表現の1バイト目(先頭バイト)の値として、既存のいわゆる半角文字のコード領域、すなわち、ASCIIコード由来の英数字・記号文字・制御文字やJIS X 0201で追加された記号・半角カナ文字などの使用している値が出現するのを避けるためである。

ISO-2022-JPなどは1バイト目に8ビット文字コードと共通する値を使用しているため、どの文字コードの文字であるかをシステムに知らせるためにコード切り替えの印(エスケープシーケンス)をその都度挿入しなければならない。

一方、シフトJISコードは1バイト目に8ビット文字と重ならないようコードを配置しているため、1バイト目を読み込んだ時点ですぐにシフトJISコードの文字であると判定でき、ASCII文字と漢字などが混在する文字列でもエスケープシーケンスを付加しなくてよいという利点がある。

ただし、2バイト目にASCII領域のコードが現れることは避けられないため、文字列データ中の任意の位置のバイトが半角文字なのかシフトJISコード文字の2バイト目なのかを他の手掛かりを用いずに知ることはできない。

また、2バイト目に16進数「5C」(92番、欧米ではバックスラッシュ、日本では円記号)が現れる文字があり、バックスラッシュや円記号にエスケープ文字などの特別な意味を与えているシステム(特に、日本語コードを考慮しない欧米製のソフトウェアなど)でうまく動作しないことがある。

歴史

シフトJISコードは1982年に日米のコンピュータ業界数社が共同で考案したとされ、米マイクロソフト(Microsoft)社が自社のパソコン向けオペレーティングシステム(OS)製品の「MS-DOS」や「Windows」に「CP932」(コードページ932)あるいは「MS漢字コード」として実装したことで広く普及した。

メーカー独自仕様だったことから長らく公的な規格とはなっていなかったが、1997年の「JIS X 0208」改訂版の附属書として仕様が掲載された。その後、2000年の「JIS X 0213」で「Shift_JISX0213」の名称で記載され、2004年のJIS X 0213改訂版では「Shift_JIS-2004」に改名されている。正式には「Shift_JIS」と間にアンダーバーを挟んで表記する。

コンピュータで文字データを扱うには、文字や記号の一つ一つに対応する番号(符号)を与え、文字の列を番号の列に変換する必要がある。文字と番号の対応関係を定めたルールを「文字コード」(character code)と呼び、従来は国や言語圏ごとに自分たちの使う文字のコード体系を定めて使用していた。

Unicodeは世界中の様々な言語の文字を集め、すべての文字や記号に重複しないようそれぞれ固有の番号を与えた文字コード規格である。世界の主な言語のほとんどの文字を収録しており、通貨記号や約物など文字と共に使われる記号や絵文字なども登録されている。

米大手IT企業を中心とする業界団体「Unicodeコンソーシアム」(Unicode Consortium)が仕様を策定・改訂しており、ほぼ同じものがISO(国際標準化機構)とIEC(国際電気標準会議)の合同委員会によって「ISO/IEC 10646」として国際標準となっている。ISO/IEC側ではUnicodeに相当する文字集合の名称を「UCS」(Universal Coded Character Set)としている。

コードポイント

Unicodeでは、登録された文字のそれぞれについて「コードポイント」(code point：符号点、符号位置と訳される)と呼ばれる一意の通し番号を与えている。例えば、日本語のカタカナの「ア」には12450番が割り当てられており、説明文などでは16進数を用いて「U+30A2」のように表記する。

世界中のあらゆる言語の文字を収録するという目的のため、コードポイントは最長で21ビットの値(上限は1114111番、U+10FFFF)まで用意されている。初期の規格で世界の既存の文字コードに規定された文字の多くが収録されたが、独自の文字コードを持たなかった言語や、絵文字、古代文字、新設された通貨記号などを中心に、現在も毎年のように新しい文字が追加されている。

現在はコードポイント空間全体の約12%にあたる約15万文字が割り当て済みで、規格上は文字を規定しない「私用面」(企業などが独自に使用してよい)が約13万文字(約12%)分予約済みである。残りの約75%が未割り当てとなっている。

基本多言語面と追加多言語面

コードポイントの範囲のうち、16ビット(2バイト)の値で表現できる U+0000 から U+FFFF は「基本多言語面」(BMP：Basic Multilingual Plane)と呼ばれる。ラテンアルファベットやキリル文字、ギリシャ文字、ひらがな・カタカナ、ハングル、基本的な漢字など、主要な言語の文字のほとんどをカバーしている。

当初の規格はBMPのみの予定だったが、追加収録を希望する文字のすべてを登録しきれないことが明らかになり、後から U+10000～U+10FFFF の拡張領域が追加された。このうち、U+10000～U+1FFFF の範囲を「追加多言語面」(SMP：Supplementary Multilingual Plane/補助多言語面)と呼び、古代文字や絵文字などが収録されている。

日本語文字の扱い

日本語の文字は原則として日本語文字コードのJIS規格から収録されている。当初は「JIS X 0201」(いわゆる半角文字)、「JIS X 0208」(JIS基本漢字)、「JIS X 0212」(JIS補助漢字)に定められた文字を収録したが、後に「JIS X 0213」(JIS2000/JIS2004)のすべての漢字が収録された。

なお、JIS X 0213の一部の漢字についてはBMPには収まりきらず、東アジア各国・地域の追加漢字を収録する U+20000～U+2FFFF の領域(SIP：Supplementary Ideographic Plane/追加漢字面)に収録されている。

これら元になった規格の通り、半角カナも全角とは別に「HALFWIDTH KATAKANA LETTER A」(半角カタカナのア)等の名称で、全角英数字も「FULLWIDTH LATIN CAPITAL LETTER A」(全角ラテンアルファベット大文字A)等の名称でそれぞれ収録されている。

UTF (Unicode Transformation Format/UCS Transformation Format)

様々な事情から、文字をデータとして実際に記録・伝送する際には、文字集合で定められたコードポイントをそのままビット列で表すのではなく、一定の手順で特定の形式に変換する。この変換手順を「符号化方式」(文字エンコーディング)という。

Unicodeにも標準の符号化方式がいくつか定められており、用途や処理の都合に応じて使い分ける。全体を総称して「UTF」と呼び、Unicodeでは “Unicode Transformation Format” の略、ISO/IEC 10646では “UCS Transformation Format” の略とされる。

UTFには「UTF-8」「UTF-16」「UTF-32」の3種類があり(UTF-7もあるがIETF独自拡張)、同じUnicode文字列でも符号化が違えばまったく異なるバイト列として表現される。文字データの保存・交換用として最も一般的に使われるのはUTF-8で、単にUnicodeといえばUTF-8でエンコードされたデータを意味することが多い。

UnicodeとISO/IEC 10646

ISO(国際標準化機構)とIEC(国際電気標準会議)の合同委員会(JTC 1)は、1980年代後半に国際的な文字コード標準の策定を目指し、仕様の検討を始めた。当初の構想は4バイトのコードを用いて既存の各国の文字コードをほとんどそのまま収録・統合するというものだった。

1991年に民間の企業連合であるUnicodeコンソーシアムが設立され、Unicode規格が発表されると、公的な標準と業界標準の分裂を避けるためISO/IECとの間で一本化の調整が行われることになった。議論の末、Unicodeの仕様をほぼそのままISO/IEC標準として採用することになった。

同年に発行されたUnicode 1.0規格をほぼそのまま取り込む形で1993年にISO/IEC 10646-1規格の初版が標準化され、以降はUnicode側と仕様を擦り合わせながら改訂されていった。両者は用語法など細かな点に違いがあるものの、収録文字など仕様の実質は同一となっている。

コンピュータで文字データを扱うには、文字や記号の一つ一つに対応する番号(符号)を与え、文字の列を番号の列に変換する必要がある。文字と番号の対応関係を定めたルールを「文字コード」(character code)と呼び、従来は国や言語圏ごとに自分たちの使う文字のコード体系を定めて使用していた。

UCSは世界中の様々な言語の文字を集め、すべての文字や記号に重複しないようそれぞれ固有の番号を与えた文字コード規格である。世界の主な言語のほとんどの文字を収録しており、通貨記号や約物など文字と共に使われる記号や絵文字なども登録されている。

米大手IT企業を中心とする業界団体「Unicodeコンソーシアム」(Unicode Consortium)が仕様を策定・改訂しており、ほぼ同じものがISO(国際標準化機構)とIEC(国際電気標準会議)の合同委員会によって「ISO/IEC 10646」として国際標準となっている。ISO/IEC側ではUCSに相当する文字集合の名称を「UCS」(Universal Coded Character Set)としている。

コードポイント

UCSでは、登録された文字のそれぞれについて「コードポイント」(code point：符号点、符号位置と訳される)と呼ばれる一意の通し番号を与えている。例えば、日本語のカタカナの「ア」には12450番が割り当てられており、説明文などでは16進数を用いて「U+30A2」のように表記する。

世界中のあらゆる言語の文字を収録するという目的のため、コードポイントは最長で21ビットの値(上限は1114111番、U+10FFFF)まで用意されている。初期の規格で世界の既存の文字コードに規定された文字の多くが収録されたが、独自の文字コードを持たなかった言語や、絵文字、古代文字、新設された通貨記号などを中心に、現在も毎年のように新しい文字が追加されている。

現在はコードポイント空間全体の約12%にあたる約15万文字が割り当て済みで、規格上は文字を規定しない「私用面」(企業などが独自に使用してよい)が約13万文字(約12%)分予約済みである。残りの約75%が未割り当てとなっている。

基本多言語面と追加多言語面

コードポイントの範囲のうち、16ビット(2バイト)の値で表現できる U+0000 から U+FFFF は「基本多言語面」(BMP：Basic Multilingual Plane)と呼ばれる。ラテンアルファベットやキリル文字、ギリシャ文字、ひらがな・カタカナ、ハングル、基本的な漢字など、主要な言語の文字のほとんどをカバーしている。

当初の規格はBMPのみの予定だったが、追加収録を希望する文字のすべてを登録しきれないことが明らかになり、後から U+10000～U+10FFFF の拡張領域が追加された。このうち、U+10000～U+1FFFF の範囲を「追加多言語面」(SMP：Supplementary Multilingual Plane/補助多言語面)と呼び、古代文字や絵文字などが収録されている。

日本語文字の扱い

日本語の文字は原則として日本語文字コードのJIS規格から収録されている。当初は「JIS X 0201」(いわゆる半角文字)、「JIS X 0208」(JIS基本漢字)、「JIS X 0212」(JIS補助漢字)に定められた文字を収録したが、後に「JIS X 0213」(JIS2000/JIS2004)のすべての漢字が収録された。

なお、JIS X 0213の一部の漢字についてはBMPには収まりきらず、東アジア各国・地域の追加漢字を収録する U+20000～U+2FFFF の領域(SIP：Supplementary Ideographic Plane/追加漢字面)に収録されている。

これら元になった規格の通り、半角カナも全角とは別に「HALFWIDTH KATAKANA LETTER A」(半角カタカナのア)等の名称で、全角英数字も「FULLWIDTH LATIN CAPITAL LETTER A」(全角ラテンアルファベット大文字A)等の名称でそれぞれ収録されている。

UTF (Unicode Transformation Format/UCS Transformation Format)

様々な事情から、文字をデータとして実際に記録・伝送する際には、文字集合で定められたコードポイントをそのままビット列で表すのではなく、一定の手順で特定の形式に変換する。この変換手順を「符号化方式」(文字エンコーディング)という。

UCSにも標準の符号化方式がいくつか定められており、用途や処理の都合に応じて使い分ける。全体を総称して「UTF」と呼び、UCSでは “Unicode Transformation Format” の略、ISO/IEC 10646では “UCS Transformation Format” の略とされる。

UTFには「UTF-8」「UTF-16」「UTF-32」の3種類があり(UTF-7もあるがIETF独自拡張)、同じUCS文字列でも符号化が違えばまったく異なるバイト列として表現される。文字データの保存・交換用として最も一般的に使われるのはUTF-8で、単にUCSといえばUTF-8でエンコードされたデータを意味することが多い。

UnicodeとISO/IEC 10646

ISO(国際標準化機構)とIEC(国際電気標準会議)の合同委員会(JTC 1)は、1980年代後半に国際的な文字コード標準の策定を目指し、仕様の検討を始めた。当初の構想は4バイトのコードを用いて既存の各国の文字コードをほとんどそのまま収録・統合するというものだった。

1991年に民間の企業連合であるUnicodeコンソーシアムが設立され、Unicode規格が発表されると、公的な標準と業界標準の分裂を避けるためISO/IECとの間で一本化の調整が行われることになった。議論の末、UCSの仕様をほぼそのままISO/IEC標準として採用することになった。

同年に発行されたUCS 1.0規格をほぼそのまま取り込む形で1993年にISO/IEC 10646-1規格の初版が標準化され、以降はUCS側と仕様を擦り合わせながら改訂されていった。両者は用語法など細かな点に違いがあるものの、収録文字など仕様の実質は同一となっている。

リレーショナルデータモデル(関係データモデル)と呼ばれる数学的なモデルに基づいてデータを秩序立てて格納したデータ集合である。一件の登録単位は複数の属性(attribute)の組(tuple)で、同じ属性を持つ組を何件も集めたデータの集合体をリレーション(関係)という。

これは実際には縦横に項目が並んだ表(テーブル)の形で整理される。リレーションが表に相当し、属性を縦方向に並んだ列(column)、組を横方向に並んだ行(row)として表す。システムによっては行を「レコード」(record)、列を「フィールド」(field)と呼ぶこともある。

実際のデータベースは「顧客マスタ」「製品マスタ」「受注明細」のように複数の表の集合として管理されることが多い。「受注明細の顧客IDは顧客マスタを参照する」といったように複数の表にまたがって同じ属性を配置し、対応付けて管理することができ、複雑なデータや大規模なデータを柔軟に取り扱うことができる。

RDBMSによる管理

関係データベースはRDBMS(Relational Database Management System：リレーショナルデータベース管理システム)と呼ばれる専用のソフトウェアによって作成・運用されることが多い。データベースの管理はRDBMSが行い、他のソフトウェアは必要なときにRDBMSへ接続して操作を依頼する。

RDMBSへの指示には「SQL」(Structured Query Language)という問い合わせ言語が標準的に用いられ、データベースの作成や削除、テーブルへのデータの追加や更新、指定した条件を満たすデータ集合の抽出などの操作を行なうことができる。

著名なRDBMSとしては、米オラクル(Oracle)社の「Oracle Database」、米マイクロソフト(Microsoft)社の「SQL Server」、米IBM社の「Db2」などの商用ソフトウェア製品、オープンソースで配布されている「MySQL」「MariaDB」「PostgreSQL」などが知られる。

個人や小集団で利用する「Microsoft Access」や米クラリス(Claris)社の「FileMaker Pro」のようなデスクトップデータベース製品や、RDBMSをクラウドサービスとして提供する米アマゾンドットコム(Amazon.com)社の「Amazon RDS」「Amazon Aurora」などもある。

歴史

関係データベースの基礎となる理論は1969年に米IBM社のエドガー・コッド(Edgar F. Codd)氏が提唱したリレーショナルデータモデル(relational data model)で、これを元に開発されたRDBMSが1980年頃から当時の大型コンピュータ向けのソフトウェアとして普及し始めた。

1990年代以降は他の方式を圧倒し、企業などが情報システムでデータの記録や管理を行う際の標準的な手法として広まった。近年では、用途によっては「NoSQL」(Not only SQL)と総称される非リレーショナル型の方式が導入される事例も増えている。

BNFは言語内で意味を持つ記号列と、それがどのような内容を取りうるのかを「<記号>::=定義」という構文を用いて列挙していく。左辺値に現れる記号は右辺値で変換可能な「非終端記号」で、右辺値にしか現れない記号はそれ以上変換できない「終端記号」である。

定義には「<居住自治体>::=<都道府県> <市区町村>」のようにスペースで区切って複数の要素の組み合わせ(連接)を置いたり、「<真理値>::=true|false」のように縦棒(|)で区切って複数の要素の選択を表すことができる。BNF内で定義する記号列は山括弧(<>)で括り、括られてない記号列は定義対象の言語における表記とみなされる。

BNFは構文を形式的に定義するための言語で、意味を規定するものではないため、BNFだけで言語のすべてを定義することはできない。プログラミング言語の定義だけでなく、プロトコルやデータ形式、マークアップ言語の定義などにも使われる。マークアップ言語として最も普及しているXMLも、その構文はBNF(正確には拡張BNF)で規定されている。

BNFは1959年にアメリカ人のジョン・バッカス(John Backus)氏が提案し、デンマーク人のピーター・ナウア(Peter Naur)氏が修正を加え、1960年にプログラミング言語「ALGOL」(ALGOL 60規格)の仕様定義のために初めて採用された。現在ではオリジナルのBNFに拡張が加えられた「拡張BNF」(EBNF)が使われることが多いが、EBNFには変種や独自拡張が多く、どの版を使用しているかに注意を払う必要がある。

通常の文字の並びの中に、「メタキャラクタ」(metacharacter)と呼ばれる特別な意味を与えられた記号などの組み合わせを埋め込む形でパターンの特徴を記述することができる。例えば、「^」というメタキャラクタは行頭を表し、「.」は任意の一文字、「+」は直前の要素の1回以上の繰り返しを意味する。

正規表現を使えば、同じ特徴を持つが細部が異なる文字列を一つの表記で同時に指定することができ、長い文章から特定のパターンに一致する箇所を抽出したり、それらを一括して同じ文字列に置換したりすることができる。例えば、「.et」という正規表現は「任意の一文字」＋「et」というパターンを表し、「net」「get」「set」「let」などに一致する。

正規表現の源流となるクリーネ閉包などの概念は1950年代の初期の計算機科学などに求めることができるが、1970年代に初期のUNIXシステム向けに開発されたテキストエディタやコンパイラ、汎用の文字列検索コマンド(grep)などを通じてその有用性が広く知られるようになり、様々な分野やソフトウェア、プログラミング言語などに普及していった。

正規表現の仕様にはPOSIXにより定義された仕様書などは存在するが、広く受け入れられた標準規格などはない状態が続いている。言語やソフトウェアによって独自の拡張が繰り返されており、基本的な共通の記法はあるものの細部の仕様は異なっている。

日常的な算術や数学では、演算子を対象の真ん中に挟む「中置記法」(infix notation)が一般的で、「1と2の和」を「1+2」のように表記する。この記法は演算子の結合順序のルール(優先順位)や括弧による計算順の指定が必要で、「1+2×3+4」と「(1+2)×(3+4)」は違う式になる。

一方、逆ポーランド表記法は演算子を後ろに置く表記法で、「1と2の和」は「1 2 +」のように表記する。四則演算などの二項演算子のみを利用する場合、結合順の指定が無くても一意に計算順序を決定できる。例えば、中置記法の「1+2×3+4」は「1 2 3 × + 4 +」、「(1+2)×(3+4)」は「1 2 + 3 4 + ×」と表記される。

値の間に必ず演算子が挟まる中置記法と異なり、値同士を並べて記述するため、どこが値の境界なのか明確になるよう区切り記号(コンピュータの場合は空白文字など)を挟むなどして分かち書きをする必要がある。

この記法はポーランドの論理学者、ヤン・ウカシェヴィチ(Jan Łukasiewicz)が考案した「ポーランド記法」(Polish notation)の逆順であるため、このように呼ばれる。ポーランド記法では「+ 1 2」のように演算子の後に被演算子の列を記載する。

ポーランド記法も逆ポーランド表記法も、コンピュータプログラムが数式を扱う際に都合が良いため、数式処理のためのデータ構造などに応用されることがある。両者の特徴はほとんど同じだが、逆ポーランド表記法はスタック構造を利用して単純な操作の繰り返しで数式を評価するプログラムを記述できるため、電卓プログラムを作るプログラミング課題などの形でよく取り上げられる。

オートマトンは一定の規則に従って複数の内部「状態」(state)の間を「遷移」(transition)する仮想的な機械で、現在の状態と入力の組み合わせを規則の中から探し出し、指定された次の状態へ遷移する。規則に該当する組み合わせがなければ同じ状態を維持する。規則は状態遷移表や状態遷移図として書き表すことができる。

有限個の種類からなる状態と入力を扱うものを「有限オートマトン」(finite automaton)という。最も単純なモデルであるためよく考察の対象となり、論理回路の設計やプロトコル(通信規約)の検証、言語の構文解析など実用上の応用も盛んに行われている。

有限オートマトンのうち、状態と入力によって次の遷移先が常に一意に定まるものを「決定性有限オートマトン」(DFA：Deterministic Finite Automaton)、次の遷移先が一意に決まるとは限らないものを「非決定性有限オートマトン」(NFA：Nondeterministic Finite Automaton)という。

有限オートマトンに無限の深さのスタックを追加した「プッシュダウンオートマトン」(push down automaton)や、複数のオートマトンを並べて相互作用させる「セルオートマトン」(cell automaton)などもよく知られている。広義には「チューリングマシン」(Turing machine)もオートマトンと一種とみなす場合もある。

様々な表現形式があるが、一般的な手法では、対象が取りうる状態を円や矩形などで列挙し、どこからどこへ遷移が起きうるかを矢印によって示す。各矢印の脇に、その遷移が起きるための条件やきっかけとなる出来事などを記述する。自らに遷移する場合は自分を指し示す輪っか状の矢印を書き入れる。

対象に開始や終了がある場合は、特殊な記号で示される場合がある。UMLでは開始を塗りつぶした丸印で、終了を内側を塗りつぶした二重丸で記載するよう定められている。

状態遷移表

状態遷移表の各状態を一行として表の形で書き表したものを状態遷移表という。

一般的な形式では、各行が対象の状態を、各列がイベントを表し、ある状態のときにあるイベントが起きたときにどの状態に遷移するかを書き入れていく。

また、縦軸・横軸ともに状態を並べ、各状態の交差する項目にそのような遷移が起こるイベントを書き入れていく様式もある。

ソフトウェア開発の分野ではテストを行う際にテストケースを漏れなく網羅するために状態遷移表が作成される場合がある。

ステートマシン図 (state machine diagram)

ソフトウェアの設計などに用いられるUML(Unified Modeling Language)では、状態遷移表に相当する図をステートマシン図(state machine diagram)として定義している。

あるオブジェクトの振る舞いを漏れなく記述するために用いられるもので、開始状態を塗りつぶした丸印(●)、終了を内側を塗りつぶした二重丸で表し、途中の状態を角丸の矩形を並べて図示していく。

状態間は遷移する方向に矢印で繋ぎ、脇に遷移の説明を添える。遷移したときに実行する動作がある場合は矩形を横に区切って下半分に動作の内容を記述する。

様々な表現形式があるが、一般的な手法では、対象が取りうる状態を円や矩形などで列挙し、どこからどこへ遷移が起きうるかを矢印によって示す。各矢印の脇に、その遷移が起きるための条件やきっかけとなる出来事などを記述する。自らに遷移する場合は自分を指し示す輪っか状の矢印を書き入れる。

対象に開始や終了がある場合は、特殊な記号で示される場合がある。UMLでは開始を塗りつぶした丸印で、終了を内側を塗りつぶした二重丸で記載するよう定められている。

状態遷移表

状態遷移図の各状態を一行として表の形で書き表したものを状態遷移表という。

一般的な形式では、各行が対象の状態を、各列がイベントを表し、ある状態のときにあるイベントが起きたときにどの状態に遷移するかを書き入れていく。

また、縦軸・横軸ともに状態を並べ、各状態の交差する項目にそのような遷移が起こるイベントを書き入れていく様式もある。

ソフトウェア開発の分野ではテストを行う際にテストケースを漏れなく網羅するために状態遷移表が作成される場合がある。

ステートマシン図 (state machine diagram)

ソフトウェアの設計などに用いられるUML(Unified Modeling Language)では、状態遷移図に相当する図をステートマシン図(state machine diagram)として定義している。

あるオブジェクトの振る舞いを漏れなく記述するために用いられるもので、開始状態を塗りつぶした丸印(●)、終了を内側を塗りつぶした二重丸で表し、途中の状態を角丸の矩形を並べて図示していく。

状態間は遷移する方向に矢印で繋ぎ、脇に遷移の説明を添える。遷移したときに実行する動作がある場合は矩形を横に区切って下半分に動作の内容を記述する。

関数を無限大など極限に飛ばしていった際に、おおよそどの程度のスピードで値が変化していくかを表す。例えば、f(x)=x²+x+1という関数のxを無限大に向けて増大させていくと、fの変化はほとんどがx²の項で決まり、第2項のxの影響は十分に小さくなる。

このことを記号「O」(ビッグオー)を用いて、f(x)=O(x²)のように記す。オーダーの評価では、最も影響の大きな項以外は無視する。また、定数の係数がある場合、定数倍の違いは極限においては大きな差ではないため無視する。

計算量のオーダー

計算機科学の計算量理論では、アルゴリズムの計算量を評価するためにこの考え方および記法を用いる。実際の計算にかかる時間はコンピュータの能力や入力するデータによって変わるが、入力するデータ量に対して計算回数がどのようなスピードで増えていくかはアルゴリズムごとに固有であるため、オーダー記法によって大まかに評価し、同種の別のアルゴリズムと比較することができる。

様々なアルゴリズムに登場する有名なオーダーには固有の名前が付けられている場合がある。最も計算量が少ないのはデータ量によらず定数回の計算で処理が完了するもので、「定数時間」と呼び「O(1)」と書き表す。

他のオーダーはデータ量n(通常はビット数)を使って表される。計算時間の短い方から、nの対数に比例する「対数時間」O(logn)、nに正比例する「線形時間」O(n)、nと対数の積に比例する「準線形時間」あるいは「線形対数時間」O(nlogn)、nの自乗に比例する「二乗時間」O(n²)、計算量が多項式で表される「多項式時間」O(n^c)(cは1以上の定数)、定数kのn乗に比例する「指数時間」O(kⁿ)、nの階乗に比例する「階乗時間」O(n!)などがよく知られる。

アルゴリズムによってはデータの規則性などによってまったく計算時間が変わることがあるため、最悪計算時間、平均計算時間、最良計算時間の3つに分けて評価する場合がある。例えば、高速な整列(ソート)アルゴリズムの代表として知られるクイックソートは、最良と平均の計算量が O(nlogn) と高速だが、特定の規則性のあるデータに対しては最悪 O(n²) かかってしまうことが知られている。

ある問題をコンピュータによって解くには、計算や操作、比較、分岐、繰り返しなど単純な処理を組み合わせたアルゴリズムを定義して、これをコンピュータプログラムの形で実装して実行する。その際、あるアルゴリズムが問題を解くにあたって実行しなければならない処理や操作などの回数(ステップ数)のことを時間計算量という。

具体的に必要な量は問題の要素数によって変動することが多いため、容量を要素数の式で表したときに支配的な大きさの項を用いて「O(項)」と表記することが多い(オーダー記法)。例えば、時間計算量がO(1)ならば要素数に依らず一定回数のステップが必要なアルゴリズムであり、O(n²)ならば要素数の2乗に比例してステップ数が増える。

一方、問題を解く際に占有する必要があるメモリ容量のことは空間計算量という。多くの問題は複数のアルゴリズムで解くことができ、空間計算量も時間計算量も少ないアルゴリズムが優れたアルゴリズムであると言えるが、一般的にはメモリを多く費やせば短時間で解け、長時間かければ少ないメモリ容量で済むという「時間と空間のトレードオフ」の関係が現れることが多い。

人類は未だに人間の脳の振る舞いや知能の仕組みを完全には解明していないため、人工知能にも明快な定義は与えられていない。また、情報技術の進歩に伴って時代によって人工知能とされるシステムの具体的な内容は大きく変化してきている。

特に、前の時代に人工知能の一分野として研究・開発が進められていたものが、技術が成熟し実用化や普及が進むと人工知能とは呼ばれなくなり、より高度で研究途上のものが新たに人工知能として注目される傾向がある。この現象は「AI効果」と呼ばれ、例として文字認識技術(OCR)や検索エンジン、かな漢字変換システム、ロボット掃除機などが挙げられる。

2000年代後半以降に人工知能とされるものは、大量のデータから規則性やルールなどを学習し、与えられた課題に対して推論や回答、情報の合成などを行う機械学習(ML：Machine Learning)を基礎とするものが主流となっている。

特に、人間の神経回路を模したニューラルネットワーク(NN：Neural Network)で深い階層のモデルを構築し、精度の高い推論を行うディープラーニング(深層学習)研究に大きな進展があり、これに基づく研究や開発が盛んになっている。

応用分野として、チェスや将棋、将棋など知的なゲームで対局するシステム、画像や映像に映る物体や人物を識別する画像認識システム(コンピュータビジョン)、人間の発話を聞き取って内容を理解する音声認識システム、言葉を組み立てて声として発する音声合成システム、ロボットや自動車など機械の高度で自律的な制御システム(自動運転など)、自動要約や質問応答システム、高度で自然な機械翻訳といった様々な自然言語処理などがよく知られる。

例えば、医師が診断に用いる知識を一定の形式でデータとして表現し、推論エンジンと呼ばれるプログラムに読み込ませる。これに対して患者が訴える症状をデータとして入力すると、知識データに基づいて推論を行い、医師が行うのと似たように診断結果を出力する。結果は一つに特定して返答する場合もあるが、複数の候補を確度の高さなどと共に提示するシステムが多い。

人間の持つ知識それ自体は高度に複雑で、様々な形態の情報の集合として表されるが、エキスパートシステムではこれを「○○ならば××である」といった単純な条件やルールに分解し、特定のデータ形式によって表現する。規則はデータ構造として表され、推論エンジンのプログラムの論理構造からは切り離されている。これによりエンジンの開発と知識ベースの作成を分離することができ、また、知識ベースを交換することで同じエンジンで様々な分野の推論を行うことができる。

1980年代のいわゆる第2次AIブームで盛んに研究・開発されたシステムだが、実際の専門知識をルールの集合として表すのが当初の想像以上に困難(一見互いに矛盾するルール群の扱いなど)であったことや、現実の問題は極めて複雑で例外が多く、期待したほど実務的な状況での成果が上がらなかったことから失望が広がり、AI研究は再び下火になっていった。

企業などの組織で各個人が日々の業務や活動の中で得る経験や知見、資料、データ、ノウハウ、コツ、トラブル解決法といった有用な情報をITシステムに記録し、他のメンバーが検索したり参照できるようにデータベース化したものを指す。

従来は暗黙知として個人の中に溜め込まれていたような情報を形式知として共有することで、業務の効率化や均質化、技能や知識の属人性の排除、組織全体として能力の底上げ、引き継ぎや新メンバーへの知識移転の効率化などが期待できる。知識ベースなどを用いて組織内の知識を管理を行うことを「ナレッジマネジメント」(knowledge management)という。

具体的な構築手法として、専用のナレッジベースツールやFAQシステム、社内Wikiなどを導入して独立したシステムとする手法のほか、グループウェアに業務システムに記録された情報を利用する手法、文書ファイル群に対するエンタープライズサーチやデータベースシステムに対するデータマイニングなどができる環境を整える手法などがある。

オブジェクト指向プログラミングの分野では、様々なクラスやオブジェクトに共通する性質をまとめ、それらの共通の親クラス(スーパークラス)として定義することを汎化ということがある。共通機能を一つのクラスにまとめることで、同じ機能を何度も重複して開発することを避けられる。

機械学習における汎化

パターン認識や機械学習の分野では、既知のパターンから特定の分類に共通する性質や法則性、規則性などを抽出して、未知のパターンの認識や分類に応用できる形にまとめることを汎化ということがある。

機械学習ではシステムに大量の学習データ(訓練データ)を与えて分類や予測を行うモデルを構築するが、最終目的は学習したことのない未知のデータに対して適切な分類や予測を行うことである。構築したモデルに未知のデータを与えたときの回答の精度を「汎化性能」という。

例えば、数字を手書きした画像と、そこに写っている数字をペアにした学習データをたくさん用意し、一定のアルゴリズム(計算手順)に従って次々にこれを処理していくと、画像のパターンから写っている数字を予測する学習モデルを作ることができる。学習済みのシステムに未知の手書き数字の画像を与えると、そこに写っている数字を推論して回答できるようになる。

従来このような仕組みを作ろうとすると、各数字の画像に現れる特徴的なパターンを人間が整理して、判断基準としてプログラムに組み込む必要があるが、機械学習ではデータから特徴を抽出して特定の結果(答え)に紐付ける操作をコンピュータが自動的に行うため、人間は学習させたい内容を表すデータを与えるだけでよい。

教師あり学習 (supervised learning)

機械学習の手法のうち、「例題と答え」という形式に整理された「教師データ」に適合するようにモデルを構築していく方式を「教師あり学習」という。例題を入力すると対応する答えを出力するようにモデルを調整していく。

人間が既に答えを知っているような判断や作業を自動化したい場合に有効な手法で応用範囲も広いが、生のデータを「例題と答えのペア」という形式に(人手によって)整理しなければならない。学習データの質や潜在的な問題点がそのまま精度や結果に反映されてしまう難点もある。

教師なし学習 (unsupervised learning)

人間が基準や正解を与えずに学習データを分析させ、システムが自律的に何らかの規則性や傾向を見出す方式を「教師なし学習」という。与えられたデータ群を何らかの目的をもって解析し、特徴の似たデータのグループ分けなどを行えるようにする。

人間にも正解が分からない課題についての知見を得たい場合や、大量のデータから規則性を探索したい場合などに有効な手法で、データの前処理が少なく現実世界にある多様な大量のデータを素材にできる。ただし、結果が何を意味するかは人間による解釈が必要で、人間にとって有用な結果が得られるよう制御するのが難しく精度も安定させにくいなどの課題がある。

強化学習 (reinforcement learning)

システムの行動に対して評価(報酬)が与えられ、行動の試行錯誤を繰り返して評価を最大化するような行動パターンを学習させる方式を「強化学習」という。機械の制御や競技、ゲームなどを行うAIの訓練に適している。

他の学習手法と異なり、人間がまとまった形で学習データを与えることはせず、システムは現在の状況を入力として行動を選択する。行動の結果は評価(値)としてシステムに伝達され、どのような行動が好ましい結果に繋がるかを繰り返し試行錯誤しながら学習していく。

人工知能・深層学習との関係

「人工知能」(AI：Artificial Intelligence)とは人間の知的な営みの一部を何らかの形で模倣するITシステム全般を指す総称であり、初期のAI研究では対象についての知識やルール、判断基準などを人間がプログラムの一部として直に記述する手法が一般的だった。

しかし、このような手法では知識の記述に手間がかかり、特定の狭い分野であっても人間のような判断を下せるシステムを実現するには途方も無い時間とコストが必要になってしまう。この限界を打ち破るため、人間は学習の仕方だけをプログラムとして実装し、実際の知識の獲得はデータを大量に与えて自動処理するという機械学習の手法が考案された。

機械学習の具体的な方式にはSVM(サポートベクターマシン)やベイジアンネットワーク、決定木(デシジョンツリー)学習、データクラスタリングなど様々な手法があるが、人間の脳の神経回路の網状の繋がりに着想を得た「ニューラルネットワーク」(NN：Neural Network)が有力な方式として台頭した。

2010年代になると、ネットワークの階層を従来より深く設定(4層以上)した「ディープニューラルネットワーク」(DNN：Deep Nueral Network)が目覚ましい発展を遂げ、機械学習研究・開発の中核として注目されるようになった。このDNNに基づく機械学習のことを「深層学習」あるいは「ディープラーニング」(deep learning)という。

学習データが「例題と答え」という形式に整理されており、例題を入力すると対応する答えを出力するようにモデルを訓練していく。答え(出力)がラベルや離散値であるようなデータを用いれば分類問題に、実数などの連続値を取るようなデータを用いれば予測や推論を行うための回帰問題に適用できる。

例えば、数字を手書きした画像(例題)と、写っている数字(答え)をペアにした教師データをたくさん用意し、画像を入力すると数字を答えるモデルを作成すると、手書きの数字を認識するシステムを作ることができる。

人間が既に答えを知っているような判断や作業を自動化したい場合に有効な手法で、様々な分野で応用が広がっている。学習効率も高く精度も向上させやすいが、生のデータを「例題と答えのペア」という形式に整理しなければならず、学習データの質や潜在的な問題点がそのまま精度や結果に反映されてしまう難点もある。

一方、人間があらかじめ正解を示さずにデータを与え、似た特徴のデータに分類する(クラスタリング)といった処理を行えるようにする手法を「教師なし学習」(unsupervised learning)、決まった正解は存在しないが出力結果に対する評価は存在し、好ましい評価を得るために出力を調整していく手法を「強化学習」(reinforcement learning)という。

与えられたデータ群を何らかの目的をもって解析し、特徴の似たデータのグループ分けなどを行えるようにする。人間が示した基準に従っているわけではないため、得られた結果が何を意味するかは人間の解釈を必要とする。

具体的な手法としては、データ群を似た特徴の集団に分類する「クラスター分析」(データクラスタリング)、多数の説明変数を要約して少ない変数で同じ傾向を説明できるようにする「主成分分析」、複数の項目間に潜在する関連性を見つけ出す「アソシエーション分析」などがある。

人間にも正解が分からない課題についての知見を得たい場合や、大量のデータから規則性を探索したい場合などに有効な手法で、データの前処理が少なく現実世界にある多様な大量のデータを素材にできる反面、人間にとって有用な結果が得られるよう制御するのが難しく精度も安定させにくいなどの課題がある。

一方、人間があらかじめ「例題と正解のペア」という形式に整理した学習データ(教師データ)を利用してモデルを訓練する手法を「教師あり学習」(supervised learning)、決まった正解は存在しないが出力結果に対する評価は存在し、好ましい評価を得るために出力を調整していく手法を「強化学習」(reinforcement learning)という。

オペレーティングシステム(OS)などの機能として提供され、一般的なコンピュータ製品とネットワーク(LAN)で利用できる簡易なものから、専用のハードウェアや接続インターフェース(インターコネクト)により構成される高度な製品まで様々な方式がある。

コンピュータ間の接続や連携などは専用のクラスタソフトが行い、利用者やソフトウェアからは一台のコンピュータとして通常と同じ方法で操作・使用することができる。クラスタリング技術により連結されたコンピュータ群を「クラスタシステム」あるいは「コンピュータクラスタ」という。

クラスタリングを行う目的によって機器の構成や運用手法は異なる。「HPCクラスタ」(High Performance Computing cluster)はスーパーコンピュータなどの構成法の一つで、多数のノードを連結して並列処理を行わせることで一台の高性能コンピュータとして運用する方式である。

「HAクラスタ」(High Availability cluster)は機器を複数用意することで可用性(availability)を高める方式で、稼働中に一台が故障してもシステムを運用したまま交換することができる。

このうち、全ノードを同時に稼働させ処理を分散する構成を「アクティブ/アクティブ構成」あるいは「負荷分散クラスタ」、いずれか一系統を通常時の稼働系として停止時には待機系に即座に移行して稼働を続行する構成を「アクティブ/スタンバイ構成」あるいは「フェイルオーバークラスタ」という。

データクラスタリング

統計学などにおけるデータ解析手法の一つで、多数のデータ群を何らかの尺度に基づいて似た特徴を持つ集団に分類する手法を「データクラスタリング」(data clustering)あるいは「クラスター分析」(cluster analysis)というが、文脈によってはこれを略して単にクラスタリングということがある。

他の学習手法と異なり、人間がまとまった形で学習データを与えることはせず、システムには自身が現在置かれている環境や状態および可能な行動の選択肢と、行動(出力)に対する評価が与えられる。システムは現在の状況を入力として行動を選択し、得られた評価を元に好ましい行動を学んでいく。

実際には、行動一回ごとにその良し悪しを評価する仕組みを用意するのは非現実的なことが多いため、連続して行動を起こした結果何らかの目標を達成(対戦に勝利する等)した場合に、遡って一連の行動に良い評価を与えるという設計にすることが多い。

近年ではニューラルネットワークの階層を深くしたディープラーニングに強化学習を組み合わせることで非常に複雑なタスクの自動化が可能なことが示され、注目が集まっている。システムが環境に働きかけて試行錯誤を行える状況に適しており、囲碁や将棋、ビデオゲームなどのプレイ、自動運転、ロボット制御などへの適用事例がよく知られる。

一つの根(ルートノード)から段階的に枝分かれしていく木構造に従って条件が整理されている。途中のそれぞれ枝分かれ(ノード)には一つの条件が書き入れられており、条件を評価してどの枝に進むかを判断する。末端(葉/リーフノード)には最終的な結果や結論が用意されている。

分類を行うものを「分類木」(classification tree)、関数の近似により推論や予測を行うものを「回帰木」(regression tree)という。扱うモデルが単純な場合は人力で木を構成することもでき、「診断チャート」「分類チャート」などの形で日常的にも馴染み深い。データ分析の分野では、学習データを元に機械学習により(巨大な)決定木を自動生成する「決定木学習」(decision tree learning)が研究されている。

決定木学習は、非線形のデータや説明変数の多い(次元の高い)データ、様々な尺度(質的変数か量的変数かなど)が混在しているデータでも扱いやすい、外れ値の影響が小さい、なぜその結論に至ったのか説明しやすいといった利点がある。ただし、分類性能は他の手法より劣ることが多く、線形データが苦手、過学習を起こしやすいといった難点もある。

決定木は分類や回帰を行うことができるアルゴリズムの一つで、一つの根(ルートノード)から段階的に枝分かれしていく木構造(ツリー)に従って条件を整理する。各ノード(枝分かれ)に書かれた条件に従って分岐を辿っていくことにより、末端の葉(リーフノード)に書かれた結論が得られる。

ランダムフォレストでは、学習したいデータからランダムに抽出したデータの組を多数用意して、それぞれについて決定木を作成する。評価を行う際には同じ入力をすべての木に与え、それぞれ得られた結果を平均したり、最も多かった結果を残すなどして最終的な結論を得る。

複数の機械学習アルゴリズムを組み合わせるアンサンブル学習の一種で、単体の決定木は過学習しやすいという弱点を補うことができる。学習や評価を高速に行うことができ、説明変数が多い場合の性能も良好、各変数の寄与度合いを説明できるといった特徴もある。

2つの特徴量で表される2次元のデータ群を線形モデルを用いて2種類のクラスに分類する場合、2つのデータ群を最もよく分離することができる直線を求めることになるが、サポートベクタマシンではその候補となる線に最も近いデータ点(これをサポートベクターという)からの距離(マージン)を算出し、両クラスのサポートベクターからの距離が最も遠くなる線を選択する。

2次元のデータを直線で分割する場合だけでなく、様々な特徴量を持つ一般の場合について、多次元空間内の超平面によって分割するモデルを得ることができる。カーネル関数という数学上のテクニックを用いることで、線形分離が困難な非線形の分類問題に適用することもできる。

他の手法に比べると、少ないデータ量でも高い精度のモデルを得ることができ、次元(特徴量の数)が増えても識別精度を維持しやすく、パラメータの調整がしやすいなどの利点がある。一方、学習データが増えると計算量が急激に増大する、原理が2クラス分類であるため多クラス分類に適用しにくい、カーネル関数の処理が重いといった難点も指摘されている。

例えば、様々な科目のテスト結果からデータモデルを作る場合、各科目の得点をそのまま説明変数とすると極めて多次元のモデルになり、分析が困難になる場合がある。このとき、数学の得点Smと物理の得点Spに強い相関があるとすると、係数PmとPpを適当に定めて Smp = PmSm + PpSp と一つの値で代表させてしまうことで、変数の数を減らすことができる。

Smpを第1主成分と呼び、PmとPpは分散を最大化するように算出される。続いて、Smpと直行する組み合わせの中から「国語と英語」のように別の主成分を見つけ出し、第2主成分とする。このプロセスを繰り返して変数の数を削減していく。一つの主成分が3変数以上の合成になることもあり、この例の「数学と物理の総合得点」のような明快な意味付けが難しい組み合わせになることもある。

主成分が含んでいる情報の大きさを「固有値」、その主成分でデータ全体のどのくらいの割合を説明できるかを「寄与率」という。第1主成分から第2、第3…と順に寄与率を累積していった値を「累積寄与率」と呼び、実用上は十分高い累積寄与率(例えば80%)に達したら残りの主成分は無視する。

一般に、回帰問題で予測精度を高めるために媒介変数を増やすなどモデルの自由度を高めることが行われるが、学習データの規模に対して詳細すぎるモデルを用意すると、外れ値やノイズ、偏りまで忠実に再現してしまい、本来データが表しているはずの傾向から却って外れてしまう現象が起きる。

このような過学習を起こしたモデルの回帰曲線は学習データのほとんどの点を通る複雑に折れ曲がった形になり、学習データに対しては完全に適合するが、未知のデータに対しては的外れな結果を返し、実地では使い物にならない状態になってしまう。

過学習を緩和する手法は様々なものが提唱されており、可能な場合は学習データを増やしたり、自由度をあえて下げて単純なモデルを使用したりする。学習データを2つに分けて片方で学習、もう片方で精度の検証を行う「交差検証」、モデルが複雑化するとそれを打ち消すようにペナルティを与える「正則化」などの技法が用いられることもある。

医療における検査などで、何らかの測定値が基準となる閾値(カットオフポイント)を超えたら異常あり(陽性)、下回れば正常(陰性)と判定することがある。その際、正常と判断したのに実際は異常だった「偽陽性」(false positive)、異常と判断したのに実際は正常だった「偽陰性」(false negative)という2種類の判定ミスが発生する。

ここでは値が高いほど異常の可能性が高い場合を考え、「実際に異常だった例を正しく異常と判定できた割合」である「TPR」(True Positive Rate：真陽性率)と、「実際は正常だった例を誤って異常と判定した割合」である「FPR」(False Positive Rate：偽陽性率)に着目する。

異常と判断する閾値を極端に高い値(例えば∞)に設定すると、全例を正常と判定するため、TPRもFPRも0となる。一方、閾値を極端に低い値(例えば-∞)にすると、今度は全例を異常と判定するため、TPRもFPRも1.0となる。閾値を低い方から次第に上げていくと、はじめにTPRが上昇し、遅れてFPRが上昇する。

この変化の様子を、縦軸をTPR、横軸をFPRとする折れ線グラフに描くと、原点と(1.0, 1.0)を結ぶ左上に膨らんだ曲線となる。これをROC曲線という。正常と異常を誤りなく見分けられる理想的な検査では、原点から垂直に直線が立ち上がり、(0, 1.0)から(1.0, 1.0)に向かって今度は水平に直線が引かれる。逆に、まったく正しく見分けられない検査では、原点からまっすぐ(1.0, 1.0)に向かう斜めの45°の直線となる。

ROC曲線から検査の良し悪しを定量的に評価するため、曲線が囲う下側の面積である「AUC」(Area Under Curve)を用いることがある。最良の検査では囲まれた部分が正方形となるためAUCは「1.0」、最悪の検査では直角二等辺三角形となるためAUCは「0.5」となる。この範囲の中で1.0に近いほど優れた検査であると言える。

ニューラルネットワークは動物の脳の仕組みを模した学習する機械の数学的なモデルで、データの入力、単純な計算、出力を連続して行うノードを脳神経(ニューロン)に見立て、これを大量に用意して網状に相互接続した構造となっている。

ノードは層状に配置され、外部から入力層のノード群がデータを受け取り、計算を行って結果を中間層に伝達し、中間層も同様に計算を行って出力層に伝達、出力層から結果が出力される。学習データを用いて計算や伝達に用いるパラメータを調整すると、推論や予測、分類などを行うシステムを構成することができる。

1950年代の研究初期に提唱されたニューラルネットワークはノード群を入力層・中間層・出力層の3層に配置した構造だったが、1990年代に複数の中間層を設けて全体を4層以上の深さにした「ディープニューラルネットワーク」(DNN：Deep Neural Network)が提唱された。これを用いて行う機械学習をディープラーニングという。

初期のDNNは性能がなかなか向上せずあまり注目されてこなかったが、2006年のジェフリー・ヒントン(Geoffrey E. Hinton)氏による「オートエンコーダ」の提案を突破口に劇的な飛躍を遂げた。2010年代以降は代表的な機械学習モデルとして活発に研究・開発が進み、有用なシステムの実用化や社会への実装も進展した。

ディープラーニングは画像認識(画像に何が写ってるのか検知する)において顕著な高性能を示したため画像処理分野での研究や応用が最初に注目され、画像認識や画像生成、文字認識、自動運転のためのセンサー技術などへの適用が進んだ。ディープラーニングを応用したコンピュータ囲碁やコンピュータ将棋のシステムがプロに勝利するなどのニュースを通じて一般への認知度も高まった。近年では機械翻訳や音声認識、音声合成、動画生成などへの応用も進んでいる。

脳の内部にはニューロンが複雑に絡み合ったネットワークが存在し、神経系を通じて体内の器官から刺激を受け取ると、細胞間で互いに電気信号を交換し合い、記憶が形成されたり発話や運動など各器官への指示が出力されたりする。

この仕組みを抽象化して数理モデルとして定式化したものや、さらにコンピュータ上のソフトウェアなどに実装して情報処理に応用したものを「人工ニューラルネットワーク」(ANN：Artificial Neural Network)という。IT分野において、文脈上、本物の神経回路網と混同する恐れが無い場合は、このANNを指して単にニューラルネットワークと呼ぶ。

ニューラルネットワークの構造

模式化されたニューラルネットワークは、神経細胞を模したノードを層状に配置した構造を持つ。各ノードは固有のパラメータに基いて比較的単純な計算を行う能力を持ち、上位層の各ノードの計算結果を入力として所定の計算を行う。計算結果は下位層の各ノードへそれぞれ固有の重み付けを行った上で出力される。

最もよく知られる順伝播型の3層ニューラルネットワークの場合、ノードは「入力層」「中間層」(「隠れ層」とも呼ばれる)「出力層」の3層に分かれて配置される。最上位のノード群は処理対象のデータの入力を受け付ける「入力層」で、対象を表すデータモデルの構造に従って数や役割が設定される。

入力層のノードはそれぞれの入力値に基いて計算を行い、結果を「中間層」の各ノードへ伝達する。中間層のノードは入力層から受け取った値を合計し、やはり同じように計算を行って結果を「出力層」の各ノードへ伝達する。出力層の計算結果がネットワーク全体の出力(回答)となる。

機械学習への応用

各ノードが行う計算式の係数や、ノード間で値を伝達する際の重み付け(ノードxからノードyへの重みがwのとき、xの出力のw倍をyの入力とする)などのパラメータ群を対象や目的に合わせて調整すると、入力データから何らかの推論や予測、分類などを得るシステムを作ることができる。

例えば、手書きの数字が書かれた画像データを入力すると、『「1」の確率が90%、「7」の確率が10%』といったように何の数字が書かれているか推論(分類)するシステムや、賃貸物件の最寄り駅と駅からの距離、広さを入力すると家賃を予測(回帰)するシステムなどを構成することができる。

パラメータを開発者が一つ一つ決定していくことも理屈の上では不可能ではないが、実用的なシステムではパラメータの数も組み合わせも膨大な数にのぼるため手動で調整するのは現実的ではなく、実際のデータを「お手本」としてパラメータ調整を自動で行う「機械学習」(ML：Machine Learning)の手法が用いられる。

ニューラルネットワークの学習手法として最も一般的な「教師あり学習」では、入力データと出力すべき「正解」データをセットにした「教師データ」と呼ばれるデータの組を用意する。初期状態では各ノードのパラメータはランダムに決定しておき、教師データを入力すると当然ながらデタラメな出力を行う。

これを「正解」の出力データと比較すると、望ましい状態からのズレを定量的に評価することができる。このズレを(少しだけ)打ち消すように、各ノードのパラメータを出力層から遡って順番に修正していく(誤差逆伝播法)。これを様々な教師データを用いて繰り返し行うことで、教師データ群の傾向を学習し、似た入力に対して似た出力を返せるようになる。

ニューラルネットワークの種類

ニューラルネットワークにはノード間の結合の仕方や学習の仕方などによって様々な種類がある。どのノードも下層のすべてのノードへ結合するものを「全結合型」、入力から出力へ一方向に信号が伝播するものを「順伝播型」(フィードフォワード型)という。最も初期に考案されたニューラルネットワークは全結合の順伝播型にあたる。

一方、順伝播型だが層間が全結合になっていないものを「畳み込みニューラルネットワーク」(CNN：Convolved Neural Network)、信号の伝播を双方向に行うものを「再帰型ニューラルネットワーク」(RNN：Recurrent Neural Network/回帰型ニューラルネットワーク、リカレントニューラルネットワーク、循環ニューラルネットワークとも)という。また、中間層が2層以上(全体が4層以上)の深い階層を構成したものは「深層ニューラルネットワーク」(DNN：Deep Neural Network/ディープニューラルネットワーク)と呼ばれる。

他にも、教師なし学習を行うための「オートエンコーダ」や「ボルツマンマシン」、DNNで強化学習を行うための「DQN」(Deep-Q-Network)、データの生成が可能な「敵対的生成ネットワーク」(GAN：Generative Adversarial Network)、複素数や複素演算を扱うよう拡張した「複素ニューラルネットワーク」など、様々な種類のニューラルネットワークが考案されている。

人間の脳の神経細胞の働きを模した機械学習モデルである人工ニューラルネットワーク(ANN：Artificial Neural Network)では、あるニューロンは上の階層の複数のニューロンから入力値を受け取る。入力値はニューロン間の繋がりの強さに応じて重み付けされて加算される。

加算された値に対して実数倍など単純な操作だけを行って次のニューロンに出力したのでは単なる線形変換の繰り返しとなってしまい、階層を深くする意味がないため、入力値の和に対して非線形な変換を行う必要がある。この変換を行うのが活性化関数である。

初期の研究では、脳のニューロンの発火(外部からの刺激によって電気信号を他のニューロンに発信する現象)を模して「ステップ関数」が用いられた。これはある閾値(しきい値、基準となる値)を超えれば「1」を、超えなければ「0」を出力する関数である。

バックプロパゲーションなどの手法を用いる場合は微分できる関数であることが望ましいため、基準値付近で急激に出力値が上昇する「シグモイド関数」あるいは「tanh関数」(hyperbolic tangent：双曲線正接関数)などが好まれる。近年では、基準値以下では0、基準値以上では線形に出力値が上昇する「ランプ関数」(ReLU：Rectified Linear Unit)や、これを曲線で近似した「ソフトプラス」がよく用いられる。

機械学習システムに用いられる(人工)ニューラルネットワークは人間の脳の神経回路のネットワークを模したモデルで、神経細胞を模したノードを層状に配置した構造を持つ。これに大量の学習データを与え、その特徴をノード間の繋がり具合(重み)として表現する。

大規模なモデルを作成するには大量の学習データや計算資源が必要となるため、事業者などが大規模なデータセットを用いて事前学習したモデルを用意し、これを利用者が自らの問題解決のために使用することが多い。

大規模なモデルは様々な利用者や用途で使えるように汎用的なデータセットで学習させることが多いため、特定の分野や対象、あるいは特定の組織内の情報には精通しておらず、必ずしも有用な結果が得られないことがある。

そこで、既存モデルの出力側に層を追加し、既存モデルに含まれる層も含めて新しいデータセットで学習し直す手法をファインチューニングという。既存モデルの持つ基本的な知識や能力はそのままに、特定の専門や組織に特化した出力が得られるようになる。

なお、既存モデルの基本的な性質を残すため、入力側の層は変更できないよう固定し、最終的な結果に影響する出力側の何層かを微調整する。既存モデルを完全に固定して再学習せず、追加した層のパラメータのみ調整する手法もあり、(狭義の)「転移学習」(transfer learning)という。

機械学習システムに用いられる(人工)ニューラルネットワークは人間の脳の神経回路のネットワークを模したモデルで、神経細胞を模したノードを層状に配置した構造を持つ。各ノードは上位層のノードから受け取った入力に単純な計算を行って下位層のノードへ伝達する。

畳み込みニューラルネットワークは入力層と出力層の間に中間層(隠れ層)が多数ある「ディープニューラルネットワーク」(DNN)の一種で、人間の視覚の働きを模した構造となっている。上位層側にノード間の結合が制約された多数の「畳み込み層」と「プーリング層」のセットが配置され、最下層の「全結合層」を通して最終的な出力が得られる。

各層の働き

畳み込み層は脳の視覚野にある「単純型細胞」の働きを模したもので、縦線、横線、曲線といった画像に含まれる断片的な小さな特徴を検知して下層のノードへ伝達する。特徴は「フィルタ」あるいは「カーネル」と呼ばれる小さな行列で表現され、画像のどの位置にどの特徴があるかを示す「特徴マップ」が下層へ送られる。

プーリング層は脳の視覚野にある「複雑型細胞」の働きを模したもので、畳み込み層から得た特徴マップに一定の演算を行ってサイズを縮小する。特徴の空間的な位置のズレを吸収し、同じ形状が画像中のどこにあっても同じように検知できるようにする(移動不変性)。

個々の畳み込み層やプーリング層は個別の特徴に反応するため、最後にすべてのノードが結合している全結合層へ様々な特徴の情報を流し込み、総合的な分類や予測などを行う。画像認識などの課題では物体の移動の影響を受けにくいため、それ以前のモデルよりも高い精度で物体の検知や分類を行うことができる。

日本語や英語などの自然言語で書かれた文章などで構成される大規模なデータセット(言語コーパス)で学習したニューラルネットワークの一種で、文章の理解や生成、要約、校正、対話、翻訳など様々なタスクをこなすことができる。

大規模言語モデルは、ある単語の並びの後に続く単語として、何を選べば最も「もっともらしい」かを確率として表現する。何らかの自然言語の入力を与えると、その内容に対する関連性、言語表現として自然さなどを勘案しながら新しい文章を出力することができる。利用者の指示に従って文字情報を生み出す生成AIとして利用されることが多い。

多くの機械学習システムでは、人間の手によって特定の課題のために調整された学習データを用いる「教師あり学習」を行うが、大規模言語モデルは文章の一部を隠して自分で「穴埋め問題」を作るなどの手法で与えられた文書データそのものを学習することができる(自己教師あり学習)。公開されている大量の文章などをそのまま学習に用いることができるため、大規模なモデルを効率的に構築することができる。

大規模言語モデルの具体的な設計(アーキテクチャ)にはいくつかの手法が提案されているが、現在主流となっているのは「Transformerトランスフォーマー」と呼ばれるモデルである。入力データ中の各要素に注目度合いに相当する重み付けを行う「アテンション」(attension)と呼ばれる機構を組み込んだモデルの一つで、並列処理しやすい構造であるため学習時間を短縮できる利点がある。

Transformerに基づいて構築された言語モデルとしては米グーグル(Google)社の「BERT」(Bidirectional Encoder Representations from Transformers)や米オープンAI(OpenAI)社の「GPT」(Generative Pre-trained Transformer)などがある。前者は同社のWeb検索サービスなどで、後者は対話的なAIチャットボット「ChatGPT」などで用いられている。

大規模言語モデルでは、学習が完了したニューラルネットワークが内部的にいくつの値(パラメータ)の組み合わせとして表現されるかを「パラメータ数」と呼び、言語モデルの規模を表している。パラメータが多いほど、豊富な語彙や知識を用いてより適格で自然な文章を生成できるとされる。現在実用化されているモデルは数億から数百億ものパラメータを持っており、十億を表す「B」(billionの頭文字)を用いて「7.5B」(75億パラメータ)のように表記する。

コンパイラは、プログラミング言語で書かれた「ソースコード」(source code)を読み込んで解析し、コンピュータが直に実行可能な機械語や、それに相当する中間言語などで記述された「オブジェクトコード」(object code)に変換する。この変換工程のことを「コンパイル」(comple)という。

コンパイラが生成したオブジェクトコードはそのままでは実行可能でない場合が多く、リンカなど別のソフトウェアを用いて、起動に必要なコードを追加したり、必要なライブラリなどを結合(リンク)したりして実行可能形式のプログラムとする。コンパイルを含む一連の工程を「ビルド」(build)という。

一方、ソースコードを読み込みながら、逐次的に実行可能コードを生成して実行するソフトウェアを「インタプリタ」(interpreter：「通訳者」の意)という。コンパイルやリンクなどのビルド工程を経ずにソースコードをいきなり実行できるため、スクリプト言語の実行環境としてよく用いられる。

様々なコンパイラ

Javaや.NET言語など、CPUやオペレーティングシステム(OS)の種類に依存しない中間形式でプログラムを配布する言語では、実行時に実行環境固有のコード形式(ネイティブコード)に変換するコンパイラを「JITコンパイラ」(Just-In-Time compiler)あるいは「実行時コンパイラ」という。この方式では、開発時にソースコードから中間形式へ、実行時に中間形式からネイティブコードへ、2段階のコンパイルを行う。

デジタル家電などの組み込みソフトウェアの開発など、開発環境と実行環境が異なる場合、開発環境上で別の環境向けのオブジェクトコードを生成する「クロスコンパイラ」(cross compiler)という。実行プログラムは対象環境に送ってテストや実行を行う。

コンパイラとは逆に、コンパイル済みのオブジェクトコードを解析して元のソースコードに逆変換するソフトウェアを「デコンパイラ」(decompiler)あるいは「逆コンパイラ」という。高水準言語ではソースコードとオブジェクトコードの各要素は一対一に対応しないため、完全な復元は難しい。特に、変数名などのシンボルはコンパイル時に失われるため、オブジェクトコードから取り出すことはできない。

人間が読み書きしやすいプログラミング言語で記述されたコンピュータプログラムを「ソースコード」(source code)というが、これはそのままではコンピュータの処理装置であるCPUが解釈して実行することはできない。

実行可能にするにはCPUが直に理解して実行することができる機械語(マシン語)で書かれた「オブジェクトコード」(あるいはネイティブコード)に変換しなければならない。この変換工程を実行開始前に専用のソフトウェアを用いて一括して行うことをコンパイルという。

今日の一般的なプログラミング言語では、コンパイルのみで起動可能なファイルを生成することは難しく、ソースコードに対する前処理(プリプロセス)を行ったり、ライブラリなど外部のプログラムを連結(リンク)する工程が必要となることが多い。コンパイルを含む一連の実行ファイル作成工程を「ビルド」(build)あるいは「メイク」(make)という。

機械語への変換にはコンパイル以外の手法もあり、実行環境側に「インタプリタ」(interpreter)などのソフトウェアを用意して実行時にソースコードを少しずつ読み込んで変換しながら同時に実行する方式などがある。スクリプト言語などでよく利用される。

事前コンパイルと実行時コンパイル

単にコンパイルという場合は、プログラムの実行開始前に明示的にコンパイラを用いてまとめてコードを変換することを指し、これを事前コンパイル(AOTコンパイル：Ahead-Of-Time compile)という。商用ソフトウェアなどでは開発者が開発時に行うことが多く、オープンソースソフトウェアなどでは利用者がソフトウェア導入(インストール)時に行うことが多い。

一方、実行開始時に実行環境に内蔵されたコンパイラがソースコードや中間コードのプログラムを読み込み、その場でコンパイルして実行する方式もある。これを「実行時コンパイル」(JITコンパイル：Just-In-Time complie)と呼び、Javaや.NETなど標準のプログラム配布形式が中間コードである言語や処理系でよく用いられる。

ネイティブコードと中間コード

いくつかの言語や処理系では、開発時には直に特定のCPU向けの機械語コード(ネイティブコード)にコンパイルせず、実在しない仮想的なCPU向けの機械語で書かれた中間コードにコンパイルする仕組みになっている場合がある。実行時に実行環境のCPU向けのコードに改めてコンパイルしてから起動する。

直にネイティブコードにコンパイルする言語では、複数の異なるCPUにプログラムを対応させたい場合はそれぞれの機種ごとにコンパイルしなおして別々の実行プログラムを生成・配布しなければならない。開発側が対応していない機種でプログラムを動作させることは原則としてできない。

一方、中間コードにコンパイルする言語では、実行環境側の処理系がその機種固有のコードにコンパイルしなおしてくれるため、開発側は中間コードで書かれた単一の配布パッケージを作成するだけで済む。開発者が個別に対応しなくても、実行環境さえ用意されていればその言語で書かれたプログラムを動作させることができる。

プログラムの処理系の場合、プログラミング言語などの人工言語で書かれたソースコードを先頭から順に一文字ずつ読み込んでいき、構文規則などに照らして意味のある単位ごとに区切っていく。例えば、「var a=99;」というコードを「var」「a」「=」「99」「;」という要素に分解する。

このようにして得られたトークンの列は「構文解析」(syntax analysisまたはparse)にかけられ、文や式ごとに分離したり、それらがどのような構造で成り立っているかが分析される。結果は構文木などの構造的なデータで表され、最適化や機械語コードへの変換といった他の処理のもとになる。

自然言語処理でも同じように、自然言語で書かれた文を一文字ずつ読み込んで、単語ごとに分解し、それぞれの品詞や変化などを確定していく処理を字句解析という。英語のように単語間に空白を挟んで「分かち書き」を行う言語では単語に分解する作業は不要だが、日本語のように続けて書く言語では単語境界を確定する「形態素解析」は重要な処理となる。

コンピュータ言語の構文解析

プログラミング言語やマークアップ言語などのコンピュータ言語で書かれた文を構成要素に分解し、要素間の関係を元に特定のデータ構造に変換する操作を構文解析という。

コンピュータ言語で書かれたソースコードに「字句解析」(lexical analysis)を行い、言語仕様上意味を成す字句の最小単位であるトークンの列に置き換える。その後、言語の構文規則に従ってトークン間の関係性を解析し、構文木などのデータ構造として表す。狭義には後者のトークンの処理のみを構文解析とする場合もある。

得られた構文木から何が行われるかは言語の種類によって異なり、プログラミング言語であればオブジェクトコード(機械語のプログラム)の生成、マークアップ言語であれば画面描画、データベース言語であればデータベースへの操作などが行われることになる。

自然言語の構文解析

英語や日本語などの自然言語における構文解析では、単語単位に分解済みの文を対象に、文法や統語論を元に単語間の関係を決定し、何らかのデータ構造で表現する。

英語のように分かち書き(単語間を空白で離す)する言語では、与えられた文を空白によって即座に単語に分割することができるが、日本語などでは前処理として文を語彙や文法に基づいて単語に切り分ける「形態素解析」が必要となる。

構文解析は各種の自然言語処理の基礎技術として重要で、機械翻訳や要約生成、自然言語検索、音声アシスタントなど様々な分野に応用されている。

例えば、コンピュータプログラムの場合、同じ機能のプログラムであれば「より高速に」「より小さいメモリ占有量で」動作する方が望ましい。このような効率のよいプログラムを作成するために、一通りの機能が実装された後に、仕様を変えずに細かな見直しを行うのが最適化である。

人間が読み書きできるソースコードを解釈し、コンピュータに適した形式(機械語コードなど)に翻訳するコンパイラやインタプリタなどのソフトウェアは、より効率的なコードを生成するために、自動的に最適化を行う「オプティマイザ」(optimizer)機能を内蔵している場合がある。

数理最適化

コンピュータ科学の分野では、ある関数を特定の条件下で最大あるいは最小とする解を求める問題を「最適化問題」という。現実の問題には数式を解析的に解くことができない問題がたくさんあり、コンピュータによって計算を繰り返して最適な入力値を探索する手法が広く応用されている。

マーケティングにおける最適化

Webマーケティングなどの分野では、広告やWebサイトなどの制作物を目的に照らして最も効果が高まるよう編集する工程を最適化ということがある。例えば、Web検索エンジンで特定のキーワードを検索した際に上位にリストされるようWebサイトを編集することを「サーチエンジン最適化」(SEO：Search Engine Optimization)という。

コンピュータプログラムの開発では、プログラミング言語で書かれたソースコードをCPUが実行可能な機械語で書かれたネイティブコードに変換する必要があるが、ソースコードをいったん中間言語のプログラムに変換し、これをネイティブコードに変換する二段階の変換を行うことがある。

中間言語は架空のCPUの機械語のような形式になっていることが多く、実際のCPU固有の機械語表現に変換するのは容易となっている。プログラムを中間形式で配布することにより、同じプログラムを様々な機種やオペレーティングシステム(OS)のもとで動作させられるようになる。

有名な例としては、Java言語のプログラム配布に用いられる「Javaバイトコード」や、.NETプログラムの配布に用いられる「CIL」(Common Intermediate Language)などがある。これらはコンパイラや仮想マシン(VM)などが自動処理することを想定した言語であり、プログラミング言語のように人間が直接読み書きすることは想定されていない。

自然言語の中間言語

自然言語の機械翻訳でも、表現を特定の言語に依存しない中間的な形式に翻訳し、これを目的の言語に再翻訳するという手法が用いられることがある。各言語について、中間言語への翻訳、中間言語からの翻訳の仕組みを整備すれば、言語同士の組み合わせをすべて翻訳可能にしなくても対応言語を増やせる利点がある。しかし、中間言語を介して必ず2回翻訳(重訳)することになるため、誤訳や細かなニュアンスの喪失が起きやすい難点がある。

コンピュータの中央処理装置(CPU/マイクロプロセッサ)は機種ごとに直に実行できる機械語(マシン語)の仕様が決まっており、機械語による命令を並べたプログラムを目的プログラムという。

物理的なプロセッサの機械語で記述されたものだけでなく、プロセッサをソフトウェア的に構築した仮想マシン(VM：Virtual Machine)向けの中間コードやバイトコードなどによるプログラムも含まれる。

オブジェクトコードの生成

一般的なソフトウェア開発では、人間が読み書きしやすく高度で抽象的な機能を備えたプログラミング言語で「ソースコード」(source code)を作成し、これをコンパイラやインタプリタなどのソフトウェアで目的プログラムに自動変換して実行可能なプログラムを作成する。

目的プログラムはコンピュータが理解できればよいため、容量や処理の効率を高めるためバイナリ形式となっており、直接表示しても人間が読み取ることは難しい。なるべく直接構成・編集したい場合は機械語を人間が読み書きすることができる最低限の文字の並びに置き換えたアセンブリ言語を用いる。

目的プログラムはプログラムの起動に必要な定形コードを先頭に付け足して実行可能ファイルにすることが多いが、実行ファイルに連結して機能を提供するライブラリファイルやクラスファイルなども内部は目的プログラムとなっている。

プログラム言語でプログラムを開発することを「プログラミング」(programming)、プログラム言語で記述したプログラムを「ソースコード」(source code)という。語彙、文法、記法などが自然言語よりも厳密に定義されており、記述したソースコードはソフトウェアによって自動的に解析、処理、変換などすることができる。

コンパイラとインタプリタ

プログラム言語は人間にとって理解、記述しやすい語彙や文法で構成された言語であり、そのままではコンピュータ(のCPU)が解釈、実行することができないため、ソフトウェアによってCPUが実行可能な言語(機械語、マシン語)によるプログラムに変換して実行される。

開発時や導入時などに一度にまとめて変換処理を行うことを「コンパイル」(compile)、そのような変換ソフトを「コンパイラ」(compiler)という。実行時に変換と実行を同時並行で行うソフトウェアを「インタプリタ」(interpreter)という。

高水準言語と低水準言語

プログラム言語は人間にとっての理解のしやすさや機械語に対する抽象度の高さによって分類されることがあり、機械寄りの言語を「低水準言語」(low-level language)あるいは「低級言語」と呼び、人間寄りの言語を「高水準言語」(high-level language)あるいは「高級言語」という。

機械語の命令コードと一対一に対応する命令語を用いてプログラム言語を行う低水準言語のことを特に「アセンブリ言語」(assembly language)と呼び、機械語への変換ソフトを「アセンブラ」(assembler)という。

プログラミングパラダイム

プログラムをどのようなものとして捉え、構築していくかについて一定の設計思想やルールがある場合が多く、これを「プログラミングパラダイム」(programming paradigm)という。複数の書き方が可能な言語は「マルチパラダイム」であるという。パラダイムに基いて言語を分類することもある。

手続きを順番に記述していく「手続き型言語」(procedural language)あるいは「命令型言語」(imperative language)や、関連するデータ群と手続き群を一つのまとまりとして捉える「オブジェクト指向言語」(object-oriented language)、プログラムを関数の組み合わせとして捉える「関数型言語」(functional language)、データ間の関係や論理を記述していく「論理型言語」(logic programming language)などの種類がある。

また、主な利用目的や主要な処理系の実装方式により分類することもあり、記述や実行の手間を軽減して迅速にプログラム開発ができる「スクリプト言語」(script language)あるいは「軽量言語」(LL：Lightweight Language)、特定の分野や処理に特化した「ドメイン固有言語」(DSL：Domain Specific Language)などの分類がある。

命令は一つずつ記述して並べることもできるが、多くの言語では複数の命令をひとまとまりの手続きに連結し、外部から一つの大きな命令のように呼び出せるようにする機構を備えている。この手続きは言語により「プロシージャ」(procedure)、「サブルーチン」(subroutine)、「関数」(function)、「メソッド」(method)などと呼ばれる。

コンピュータ(のCPU)が直に解釈・実行できる機械語(マシン語)のほとんどは命令型の言語体系となっており、CPUが行うべき処理の内容を一つずつ命令として記述して順に並べることによりプログラムを構成する。手続型言語は機械語をより人間に扱いやすく翻訳したものと言え、機械語そのものでは記述が難しい複雑な構造のプログラムや大規模なプログラムの開発を容易にしてくれる。

広義の手続型言語には、手続きと関連するデータを一つの単位にまとめるオブジェクト指向の手続型言語を含むが、文脈によっては「手続型言語」が非オブジェクト指向型の手続型言語を指し、オブジェクト指向言語と対比される場合がある。

在来型の手続型言語にはAdaやFortran、ALGOL、PL/I、C言語、COBOL、BASIC、Pascalなどがあり、オブジェクト指向型の手続型言語にはC++言語やJava、C#、Visual Basic、Perl、Python、Ruby、JavaScript、PHP、Go言語、Rustなどがある。

一方、手続型言語あるいは命令型言語とは異なる体系の言語を「非手続き型言語」(non-procedural language)あるいは「宣言型言語」(declarative language)と総称する。命令の列挙以外の方法でプログラムを構成する言語で、「関数型言語」(functional language)や「論理型言語」(logic programming language)、「問い合わせ言語」(query language)などを含む。

プログラミング言語の多くは手続き型(procedural)あるいは命令型(imperative)と呼ばれる形式で、コンピュータに対する動作の指示を一つずつ順番に並べるスタイルでプログラムを記述していく。

これに対し関数型言語ではプログラムを、引数を入力として処理を行い、呼び出し元に返り値を出力する関数(function)の組み合わせとして記述する。手続き型でも関数の仕組みは利用できるが、関数型言語はほとんどありとあらゆるものを関数の定義と関数呼び出しを用いて実現する点で徹底している。

例えば、同じ処理を規定の回数や条件に従って繰り返す反復処理は、手続き型では一般的にfor文やwhile文などの制御構文を用いるが、関数型言語では関数の再帰呼び出しによって実装される。

関数型言語の主な特徴

関数型言語の多くに共通する特徴として、関数を変数と同じようにほとんどの操作が可能な第一級オブジェクト(first-class object)として扱う点があり、関数を引数や返り値とする「高階関数」(higher-order function)を定義することができる。

また、変数や関数の引数、返り値などを記述する際に、明示的にデータ型を宣言しなくても処理系が自動的に推定して適した処理を行ってくれる「型推論」(type inference)の機能もほとんどの言語が持っている。

参照透過性と純粋関数型言語

同じ入力には必ず同じ作用と出力を返す性質を「参照透過性」(referential transparency)と呼び、参照透過な記述のみで構成されたプログラムは、その評価や実行が以降の処理に思わぬ影響を及ぼす「副作用」(side effect)のないプログラムとなる。

関数型言語ではすべてを関数とすることで参照透過性を保ちやすくなっており、手続き型のプログラミングで開発者を悩ませ続ける副作用の問題を解消しやすい。ただし、外部との入出力など参照透過性を維持するのが本質的に難しい場面もあるため、多くの関数型言語は実用性との兼ね合いから参照透過的でない記述ができるようになっていることが多い。

参照透過的な記述しかできないようになっている言語を「純粋関数型言語」と呼び、Haskellがよく知られる。そうでないものは「非純粋関数型言語」と呼ばれ、Lisp、Scheme、ML(Meta-Language)、OCaml、Scala、Clojure、Erlang、F#など、よく知られる関数型言語のほとんどはこちらに分類される。

関数型言語と関数型プログラミング

関数型言語の研究や普及が進むに連れて、手続き型など他の種類のプログラミング言語にもその特徴が取り込まれるようになってきており、無名関数や高階関数、型推論などは多くの言語に実装されている。

「関数型プログラミング」とは関数型言語によるプログラミングだけでなく、手続き型言語などを用いて関数を組みわせてプログラムを構成する手法が含まれる。逆に、形式的には関数型言語を使っていても、代入など手続き型の特徴ばかりを用いてプログラムを構成していれば、それはもはや関数型ではなく手続き型プログラミングであると言える。

オブジェクト指向プログラミング(OOP：Object-Oriented Programming)はコンピュータプログラムの構成法の有力な一方式で、データと手続き一体化したオブジェクト群を定義していき、それらが互いに指示やデータを送り合うことにより処理を進めていく。

オブジェクト指向言語はこのような開発方式に必要な諸機能を言語仕様として備えているものを指し、オブジェクトの雛形であるクラス(class)やプロトタイプ(prototype)、および内部のメソッド(method)やプロパティ(property)を定義する構文や、オブジェクトのインスタンス化、メソッド呼び出し、メッセージ交換などの機能を提供する。

オブジェクトの定義にクラスを用いる言語とプロトタイプを用いる言語に分けられ、C++言語やC#、Javaなどは前者、JavaScriptやRuby、Pythonは後者に分類される。

C言語を拡張してオブジェクト指向性を持たせたC++やObjective-C、ML(Meta-Language)を拡張したOCaml、Pascalを拡張したObject Pascalのように、既存の言語にオブジェクト指向性を追加した言語もある。

オブジェクト指向という性質は手続き型や関数型などプログラミング言語における他のスタイルと共存することができる。オブジェクト指向の手続き型言語が多いが、前述のOCamlのように関数型かつオブジェクト指向の言語などもある。

これに対し、送信者と受信者が固定されておらず、接続されたどの主体からも発信することができるような方式を「双方向通信」(duplex communication)あるいは「複信」「デュプレックス通信」などという。

トランシーバーのように、同時に一方向にしか通信できないが、通信方向を切り替えて交代で送信することができる方式もあり、双方向通信の一種とみなす立場では「半二重通信」(half-duplex)と呼ぶが、特定小電力無線やアマチュア無線ではこの方式は単方向通信に区分されることが多い。

なお、英語では “communication” という語自体に双方向的な意味合いが含まれるため、単方向の伝送は “simplex transmission” などとする場合もある。

例えば、トランシーバーはあるチャンネルで一人が話している間は他の人が同時に話すことはできず、一人ずつ交代で話さなければならない。このような通信方式を半二重という。一方、電話はどちらの話者も同時に話すことができ、自分が話している間も相手からの声を聞くことができる。このような通信方式は全二重(full duplex：フルデュプレックス)通信という。

半二重は伝送路を一つだけ用意すれば通信できるので低コストで簡易な機器や配線で利用できるが、通信方式によっては複数の主体が同時に通信を試みて信号が衝突(collision)したり混信するのを回避する制御や仕組みが必要になる場合がある。

例えば、電話はどちらの話者も同時に話すことができ、自分が話している間も相手からの声を聞くことができる。このような通信方式を全二重という。一方、トランシーバーはあるチャンネルで一人が話している間は他の人が同時に話すことはできず、一人ずつ交代で話さなければならない。このような通信方式は半二重(half duplex：ハーフデュプレックス)通信という。

全二重を実現する最も単純な方式として、2本のケーブルを一対として用い、一方を送信専用、もう一方を受信専用にするといったように物理的に異なる伝送路を用意する方式がある。一つの伝送路を共用しなければならない場合には、極めて短い時間ごとに伝送方向を切り替える時分割複信(TDD：Time Division Duplex)や、周波数帯域を二分割して双方が異なる帯域で送信する周波数分割複信(FDD：Frequency Division Duplex)などの手法が用いられる。

電気信号が発明された当初は、信号をそのまま媒体を通じて伝送する「ベースバンド伝送」という方式が用いられた。例えば、電話システムは音波を同じ周波数および波形の電気信号に変換し、電線を通じて伝送していた。現代でも電子基板内部の信号伝送やコンピュータネットワークではベースバンド伝送が用いられることがある。

一方、電波や光を用いた通信では、伝送したい信号(ベースバンド信号)が伝送媒体の物理的な特性に適さなかったり、利用可能な周波数が限られていたりすることがあり、伝送可能な基本信号(特定の周波数の正弦波など)を用意して、その状態をベースバンド信号に合わせて時系列に変化させて伝送する方式が考案された。

伝送する基本信号を「搬送波」(carrier wave：キャリア)と呼び、搬送波の振幅や周波数、位相などを運びたい信号に合わせて刻々と変化させる操作を「変調」(modulation)という。受信側では送信時とは逆に、搬送波の時系列の変化を検知してベースバンド信号を復元する操作を行う。これを「復調」(demodulation)という。両者を合わせて「変復調」という。

変調を行う装置や回路を「変調器」(modulator)、復調を行う装置や回路を「復調器」(demodulator)という。放送など送信側と受信側の設備が分かれている場合は一台の機器にどちらか片方の機能のみが搭載されるが、通信では送信と受信を行う必要があるため、両者を一体化した「変復調器」(モデム：modulator-demodulator)が用いられる。

電気通信が発明された当初は、音波を同じ周波数および波形の電気信号に変換しただけのアナログ電話のように、伝送したい信号を(無変調で)そのまま送る「ベースバンド伝送」が一般的だった。これは現代でもイーサネット(Ethernet)のような有線のデジタル通信などで行われることがある。

一方、電波や光を用いた通信では伝送したい信号(ベースバンド信号)が伝送媒体の物理的な特性に適さなかったり、利用可能な周波数が限られていたりすることがあり、伝送可能な基本信号(特定の周波数の正弦波など)を用意して、その状態をベースバンド信号に合わせて時系列に変化させて伝送する方式が考案された。

伝送する基本信号を「搬送波」(carrier wave：キャリア)と呼び、搬送波の振幅や周波数、位相などを運びたい信号に合わせて刻々と変化させる操作を変調という。受信側では送信時とは逆に、搬送波の時系列の変化を検知してベースバンド信号を復元する操作を行う。これを「復調」(demodulation)という。

変調を行う装置や回路を「変調器」(modulator)、復調を行う装置や回路を「復調器」(demodulator)という。放送など送信側と受信側が分かれている場合は一台の機器にどちらか片方の機能のみが搭載されるが、通信では送信と受信を行う必要があるため、両者を一体化した「変復調器」(モデム：modulator-demodulator)が用いられる。

元の信号がアナログである場合を「アナログ変調」(analog modulation)、デジタルである場合を「デジタル変調」(digital modulation)という。また、搬送波は通常は正弦波だが、電気通信で矩形波(パルス)を用いる場合を「パルス変調」(pulse modulation)という。

電波や光を用いた通信では、送信したい信号(ベースバンド信号)をそのまま物理的な波にして送るのではなく、「搬送波」(carrier wave：キャリア)と呼ばれる特定の周波数の正弦波を用いて、その振幅や周波数、位相などを変化させて信号を表現する。

送信側では用意された搬送波に対して時系列に変化を加える「変調」(modulation)という操作を加え、ベースバンド信号を搬送波に乗せていく。受信側では送信時とは逆に搬送波の時系列の変化からベースバンド信号を取り出す。この操作を復調という。

放送など送信と受信が分かれた一方向の通信では、送信側は変調だけを、受信側は復調だけを行う機器を用いるが、双方向通信では同じ機器が送信と受信を行う必要があるため、単一の装置が変調器(modulator)と復調器(demodulator)の両方の機能を兼ねている。これを「変復調装置」(モデム/modem：modulator-demodulator)という。

無線や光などを用いた通信では、伝送に用いる「搬送波」(carrier wave：キャリア)を用意し、その特性を時系列に変化させることで伝送したい情報を表現する「変調」(modulation)が行われる。搬送波の振幅の変化で情報を表すのが振幅変調である。

送信したいベースバンド信号の電圧の上下に従って搬送波の振幅を増減させ、信号を搬送波の振幅の頂点の推移に置き換えて伝送する。AMラジオ放送や航空無線、アナログテレビ放送の映像部分などで用いられる。

比較的単純な回路で実装でき、同じ周波数帯で複数の信号が混信しても混ざり合って受信される(弱い方が完全に消えてしまうことがない)という特徴がある。しかし、搬送波の強度が一定しないためノイズに弱い(除去しにくい)という難点もある。

無線や光などを用いた通信では、伝送に用いる「搬送波」(carrier wave：キャリア)を用意し、その特性を時系列に変化させることで伝送したい情報を表現する「変調」(modulation)が行われる。搬送波の周波数を一定の範囲で変化でさせることで情報を表すのが周波数変調である。

送信したいベースバンド信号の電圧の上下に従って搬送波の周波数を増減させ、信号を搬送波の疎密に置き換えて伝送する。FMラジオ放送やアナログテレビ放送の音声部分、アマチュア無線などで用いられる。

振幅変調(AM)と異なり搬送波の強度が一定で、常に最大の電力で送信できるため受信品質が安定し、ノイズの除去がしやすいという特徴がある。ただし、混信した場合に強度の弱い信号が完全に隠れてしまうという「弱肉強食」特性がある。放送などの用途ではその方が望ましいが、航空無線がFMではなくAMを使うのは意図せず周波数が重なった時に完全に無通信になるのを避けるためであるとされる。

音波をマイクなどでアナログ電気信号に変換し、その強度をサンプリング周波数に従って一定周期で測定する。各測定値は定められた量子化ビット数の範囲で整数値として記録する。

例えば、CDの音声はサンプリング周波数44.1kHz(キロヘルツ)、量子化16ビットのパルス符号変調方式で記録される。これは毎秒44,100回信号を測定し、その強度を65,536(2¹⁶)段階の値で表していることを意味する。

サンプリング周波数と量子化ビット数を高めるほど高品質のデータを得ることができるが、その分データ量は増大する。標本化定理により、サンプリング周波数の半分の周波数までの信号は再現可能とされており、これを「ナイキスト周波数」という。

音声の場合は人間の可聴音の上限が20kHz程度であることが知られており、40kHzを超えるサンプリング周波数を用いれば録音データからおおむね自然な音が再生できるようになると言われる。

通常のパルス符号変調方式は「リニアPCM」(LPCM：Linear PCM)とも呼ばれ、毎回の標本化で得られたデータを単純に順番に並べた形式だが、一つ前のデータとの差分を記録していく方式を「DPCM」(Differential PCM：差分PCM)という。

さらに、DPCMの各標本の量子化ビット数を直前の標本の変動幅に応じて適応的に変化させる方式を「ADPCM」(Adaptive Defferential PCM：適応的差分PCM)という。PCMとほぼ同じ品質を保ちながら符号化後のデータ量を削減できるため、実用上はこちらが用いられることも多い。

通信事業者の広域回線網や企業などの組織内のコンピュータネットワークなどでは、末端のアクセス回線は多数の低速回線、中心部分の基幹回線や拠点間接続網は少数の高速回線という構成になっていることが多い。

末端からの多数の通信の流れを通信拠点で束ねて大容量の回線でまとめて送り、相手先近くの拠点で分離してそれぞれの宛先まで届けるという制御が行われる。個々の信号やデータの流れを専用の機器などで束ねる操作を多重化、バラして一本ずつを取り出す操作を多重分離という。

また、一対の機器が単一の伝送路で接続されている際、双方向に通信するために、互いに逆方向の通信を一つに束ねる手法としても多重化が用いられる。

多重化を行うための機器や装置、素子、機構などのことを「マルチプレクサ」(multiplexer/mux)、多重分離を行うものを「デマルチプレクサ」(demultiplexer/demux)という。

多重化方式

多重化は伝送路を物理的な特性によって論理的な小さな伝送単位に分割し、それぞれを信号やデータの流れに割り当てることによって行われる。主な方式として、搬送波の周波数帯を分割して割り当てる「周波数分割多重」(FDM：Frequency Division Multiplexing)、通信時間を細かく分割する「時分割多重」(TDM：Time Division Multiplexing)などがある。

空間的に伝送路を分ける「空間分割多重」(Spatial Division Multiplexing)が行われる場合もある。これは有線通信の場合は単純に複数の通信線やケーブルを使い分けることを指すが、無線通信では複数のアンテナの指向性や位相のずれを利用して、各アンテナがそれぞれ異なる方向にある機器とのみ通信する手法を指す。

物理的な分割に依らない手法として無線通信で行われる「符号分割多重」(Code Division Multiplexing)がある。これは複数の主体が同じ周波数帯で同時刻に通信するが、通信主体ごとに割り当てられた互いに異なる符号と一定の演算を行うことで自分宛ての信号列だけを取り出すことができる。

多元接続

多重化を応用して、一つの回線や通信媒体を複数の機器や利用者で共有し、それぞれ独立に接続できるようにすることを多元接続(MA：Multiple Access)という。

FDMを利用した多元接続はFDMA(周波数分割多元接続)、TDMを利用した多元接続はTDMA(時分割多元接続)というように、それぞれの多重化手法に対応する多元接続方式が存在する。

CDMから発展したCDMA(符号分割多元接続：Code Division Multiple Access)が第3世代(3G)以降の携帯電話・移動体データ通信で広く用いられている例が有名である。

冗長化の意

コンピュータシステムの分野では、機器や回線などを複数用意して負荷分散を図ったり耐障害性を高める冗長化(二重化や三重化など)のことを多重化ということがある。

電気信号や電波など搬送波の周波数帯域を複数に分割し、それぞれ別の信号を送る方式である。例えば、テレビ放送やラジオ放送では電波の周波数帯を「チャンネル」という単位に分割し、それぞれ異なる映像や音声を発信している。

FDMを用いて複数の通信主体による通信を多重化し、同一の伝送路を共用できるようにすることを「周波数分割多元接続」(FDMA：Frequency Division Multiple Access)という。例えば、携帯電話の通信方式の中には、基地局が周囲の端末とそれぞれ異なる周波数帯を利用して同時に通信するものがある。

また、FDMと同じように一つの伝送路に二つの異なる周波数の信号を流し、一方を送信に、もう一方を受信に用いて同時に双方向通信(全二重通信)を行うことを「周波数分割複信」(FDD：Frequency Division Duplex)という。混信を防ぐため送信側と受信側の間に利用しない帯域(ガードバンド)を設ける必要がある。

なお、光通信の場合は周波数ではなく波長に着目し、複数の異なる波長の光信号を同時に一本の光ファイバーに通す方式を「波長分割多重」(WDM：Wavelength Division Multiplexing)という。

デジタル信号の多重化などで用いられる方式で、伝送路の利用権を極めて短い時間ごとに均等に分割して複数の信号に順番に割り当てる。この区切られた単位時間のことを「タイムスロット」(time slot)ということがある。

TDMを用いて複数の通信主体による通信を多重化し、同一の伝送路を共用できるようにすることを「時分割多元接続」(TDMA：Time Division Multiple Access)という。例えば、携帯電話の通信方式の中には、基地局が周囲の端末と同じ周波数を短時間ごとに切り替えて同時に交信するものがある。

また、TDMと同じように一つの伝送路の通信時間を短い単位で区切り、送信と受信を交互に切り替えて双方向通信を行う方式を「時分割複信」(TDD：Time Division Duplex)という。混信を防ぐために送信と受信の間に短時間の無通信時間を挟む必要があり、これを「ガードインターバル」(guard interval)という。

データを記憶装置に書き込んだり、電気回路や通信回線などを通じて伝送すると、様々な理由で意図せずデータの欠落や改変が起こることがある。これを完全に防止することは困難であるため、読み出しや受信の際に誤りが起きたかどうかを確かめられるようにするのが誤り検出技術である。

データを記録・送信する際に、一定の長さごとに特定の計算手順で「誤り検出符号」を算出し、データに連結する。読み込みや受信の際にはデータと符号を分離し、一定の計算手順でデータに誤りがないか確認し、誤りが検出されたら利用者にそのことを知らせたり、通信の場合は送り手に再送を要求する。

誤り検出には様々な方式があるが、どのような量・種類の誤りも完全に検出できる誤り検出符号はなく、ある長さあたり何ビットまでの誤りを検出可能かが符号により決まっている。符号を長くすれば検出できる誤りも増えるが、符号の算出・逆算のための計算量が増え、記録や伝送により多くの容量や帯域が必要となるため、コストや誤りの発生率などを勘案して適切なものが選ばれる。

著名な誤り検出符号としては、パリティ符号やチェックサム、巡回冗長符号(CRC：Cyclic Redundancy Code)などがある。誤りを検出するだけでなく、少ない誤りであれば正しい状態に復元することができる手法を「誤り訂正」(error coorection)という。検出と訂正を合わせて「誤り検出訂正」(error detection and correction)と総称する場合もある。

データを記憶装置に書き込んだり、電気回路や通信回線などを通じて伝送すると、様々な理由で意図せずデータの欠落や改変が起こることがある。これを完全に防止することは困難であるため、読み出しや受信の際に誤りが起きたかどうかを検知し、ある程度の誤りは訂正することができるようにするのが誤り訂正技術である。

データを記録・送信する際に、一定の長さごとに特定の計算手順で「誤り訂正符号」を算出し、データに連結する。読み込みや受信の際にはデータと符号を分離し、一定の計算手順でデータに誤りがないか確認し、誤りが検出されたら符号を元に復元を試みる。

誤り訂正符号の算出手法には様々な方式があるが、どのような量・種類の誤りも完全に検出・訂正できる符号はない。ある長さあたり何ビットまでの誤りを検出可能か、何ビットまでの誤りを訂正可能かが符号により決まっている。一般に、検出可能なビット数は訂正可能なビット数よりも多い。

方式によっては符号を長くすれば検出・訂正できる誤りを増やすことができるが、符号の算出・検証のための計算量が増え、記録や伝送の際に符号のために余計に費やされる容量や帯域(オーバーヘッド)も大きくなる。コストや誤りの発生率などを勘案して適切なものが選ばれる。

著名な誤り訂正符号には「ハミング符号」や「水平垂直パリティ符号」「リードソロモン符号」「BCH符号」などがある。受け手側で誤りを検知できるが訂正できない手法は「誤り検出」(error detection)と呼ばれ、誤ったデータは破棄して相手に再送を要求できる双方向通信などでよく用いられる。訂正と検知を合わせて「誤り検出訂正」(error detection and correction)と総称することもある。

パリティを含めたデータ全体で常に「1」の数が偶数になるようにパリティビットを決定することからこのように呼ばれる。例えば、もとのビット列が「0000」(「1」が0個)や「1010」(2個)、「1111」(4個)など場合にパリティビットが「0」に、「0001」(1個)や「1110」(3個)などの場合に「1」にセットされる。

一方、これとは逆に、ビット列の「1」の個数が偶数個ならパリティビットを「1」に、奇数個なら「0」に設定する方式を「奇数パリティ」(odd parity)という。一般的には奇数パリティより偶数パリティの方がよく利用される。

パリティを含めたデータ全体で常に「1」の数が奇数になるようにパリティビットを決定することからこのように呼ばれる。例えば、もとのビット列が「0001」(「1」の数が1個)や「1110」(3個)などの場合にパリティビットが「0」に、「0000」(0個)や「1010」(2個)、「1111」(4個)などの場合に「1」にセットされる。

一方、これとは逆に、ビット列の「1」の個数が奇数個ならパリティビットを「1」に、偶数個なら「0」に設定する方式を「偶数パリティ」(even parity)という。一般的には奇数パリティより偶数パリティの方がよく利用される。

誤り検出符号はデータの伝送や記録、複製が正確に行われたかを調べる手法で、送信や記録の前に検査用の値を算出して元データに付加し、受信や読み出しの際に同じ箇所のデータについて同じ手順で値を算出する。

両者が一致すれば誤りが無いことが分かり、しなければ途中でデータの一部が欠落や変化していることが分かる。CRC符号は誤り検出用の符号であり、正しい値へ訂正する機能はない。

CRCでは調べる対象のデータを一定のビット数ごとに区切って2進数の値とみなし、それより短いビット数のある定数(生成多項式と呼ぶ)で割った余りを検査用の値とする。単純なチェックサムやパリティチェックなどの方式に比べ、一か所に連続して集中的に発生するバースト誤りの検知に強いという特徴がある。

CRCの算出方法には、データをどのくらい長さで区切り、どのような定数で割るかによって様々な種類がある。どのような方式が適しているかは状況によって異なるため、通信規格などで算出方法を個別に定めることが多い。

検査用の値がnビットになるCRCを「nビットCRC」あるいは「CRC-n」のように呼び、8ビットや16ビット、32ビットなどがよく用いられる。定数の長さはn+1ビットとなり、例えば8ビットCRCであれば9ビットの定数を用いる。同じ8ビットCRCでも定数が異なる複数の方式が存在する。

データを送受信する際に、本来のデータに一定の手順で計算したチェック用のデータを付加して送信することにより、受信側で受け取ったデータに誤りがないかどうかを検証することができる。

パリティチェックでは元のビット列中の1の数が偶数なら0、奇数なら1(あるいはその逆)となる1ビットのパリティビットを付加するが、ハミング符号では元のビット列の中からいくつかの異なる複数ビットの組み合わせを考え、それぞれについてパリティを算出して付加していく。受信側では複数あるパリティから元のビット列のどこに誤りが生じたかを知ることができる。

ハミング符号は元のデータを一定の長さごとに区切って算出する。ブロックの長さと追加する符号の長さによって誤り検出能力は異なる。最も単純な例として知られる元のデータ4ビットにつき3ビットのハミング符号を算出する方式では1ビットの誤りを検知し、これを正しい値に訂正できる。

ハミング符号は1950年に米AT&T(当時)ベル研究所のリチャード・ハミング(Richard W. Hamming)氏によって考案された。後に開発されたリードソロモン符号などに比べ誤りの検出・訂正能力は弱いが、計算手順が短く高速に処理できるという特徴がある。ECCメモリやRAID 2などの採用例が有名。

データはコンピュータ上では「0」と「1」が並んだビット列として表されるが、これを一定の長さのブロックごとに区切り、各ビットの値を足し合わせた値が奇数であるか偶数であるか(「1」の数が奇数か偶数か)を表す1ビットの値(パリティビット)を末尾に付加する。

パリティを含むデータを受け取った側は、各ブロックごとに同じようにパリティを算出し、付加されたものと比較する。両者が一致すれば、そのブロックには誤りが存在しないか偶数個あることが分かり、一致しなければ奇数個の誤りがあることが分かる。

実用上、短く区切られたブロック中に同時に複数の誤りが生じる確率は低いため、パリティが一致すれば誤りが無く、一致しなければ1ビットの誤りが生じたとみなしてデータの再送や破棄などの制御を行う。

偶数パリティと奇数パリティ

パリティビットの値は、ブロックの各ビットとパリティを足し合わせた時、その偶奇性が常に同じになるように設定される。

全体の和が偶数になるように決められる(ブロック中の1の数が奇数なら1、偶数なら0)ものを「偶数パリティ」(even parity)、奇数になるように決められる(1の数が奇数なら0、偶数なら1)ものを「奇数パリティ」(odd parity)という。

水平パリティと垂直パリティ

一定の長さのブロックごとにパリティを算出して末尾に付加する方式を「垂直パリティ」(vertical parity)と呼び、単にパリティチェックといった場合はこの方式を指すことが多い。

一方、連続する数ブロックごとに、各ブロックの同じ位置にあるビット群をグループ化してパリティを算出・付与する方式を「水平パリティ」(horizontal parity)という。

両者を併用した「垂直水平パリティ」が用いられる場合もあり、パリティ用の記憶容量は約2倍必要になるが、同じブロック中の偶数個の誤りを検出したり、1ビットの誤りの訂正を行うことができる。

データを記憶装置に書き込んだり、電気回路や通信回線などを通じて伝送すると、様々な理由で意図せずデータの欠落や改変が起こることがある。これを完全に防止することは困難であるため、読み出しや受信の際に誤りが起きたかどうかを検知し、ある程度の誤りは訂正することができるようにするのがECCである。

データを一定の長さごとに区切り、一定の手順で計算を行ってECCを算出し、元のデータに付加して一緒に記憶媒体への書き込みや回線を通じて送信を行う。読み込みや受信の際にはデータと符号を分離し、一定の計算手順でデータに誤りがないか検証し、誤りが検出されたら符号を元に復元を試みる。

ECCには様々な方式があるが、どのような量・種類の誤りも完全に検出・訂正できる符号はない。ある長さあたり何ビットまでの誤りを検出可能か、何ビットまでの誤りを訂正可能かが符号により決まっている。一般に、検出可能なビット数は訂正可能なビット数よりも多い。

方式によっては符号を長くすれば検出・訂正できる誤りも増えるが、符号の算出・検証のための計算量が増え、記録や伝送の際にECCのために余計に費やされる容量や帯域(オーバーヘッド)も大きくなる。コストや誤りの発生率などを勘案して適切なものが選ばれる。

著名なECCには「ハミング符号」や「水平垂直パリティ符号」「リードソロモン符号」「BCH符号」などがある。誤りを訂正することはできず、検出のみが可能な符号もあり、「誤り検出符号」(EDC：Error-Detecting Code あるいは Error-Detection Code)と呼ばれる。

最も単純な誤り検出方式の一つで、データの伝送や記録、複製が正確に行われたかをある精度で調べることができる。誤りの検出精度は低いが原理が簡単で容易に実装でき、計算コストも低いため、簡易な誤り検出方式として広く普及している。

送信や記録の前にチェックサムを算出して元データに付加し、受信や読み出しの後に同じ個所のチェックサムを算出しなおしてみて、両者が一致しなければ、その区間に含まれるデータのいずれかに誤りが生じていることが分かる。チェックサムは誤りの検出のみ可能であり、訂正はできない。

例えば、4バイトのデータ列「C0 A8 FF 58」(16進数表記)から1バイトのチェックサムを算出するには、C0+A8+FF+58を計算して和(2BF)を求め、これを100で割った余り(最下位バイト)の「BF」がチェックサムとなる。データ列が長い場合は一定の大きさごとに区切ってチェックサムを算出・付加することが多い。その際の区切りの長さやチェックサム自体の長さは用途や実装により異なる。

なお、「チェックサム」という用語を誤り検出符号という意味で用いる場合がある。例えば、ファイルの同一性の検査のために、ファイルの内容からハッシュ関数のMD5で算出したハッシュ値を付加することがあり、これを「MD5チェックサム」と呼ぶことがある。この場合、計算手順としてのチェックサムは用いられていない。

調歩同期では、伝送を開始する際にまずスタートビットを送り、続いて一文字分のデータ(7～8ビット)、最後にストップビットを送る。データの末尾にパリティビットなど誤り検出符号を付加する場合もある。何文字も送る場合はこのプロセスを文字数の分だけ繰り返す。伝送する情報がないときにはストップビットを送り続けておく。

調歩同期のスタートビットには「0」が、ストップビットには「1」が使われることが多いが、これ以外の組み合わせの場合や、ストップビットに1.5ビットや2ビットを用いる伝送系もある。

調歩同期は制御用の信号線が不要で回線や回路の構造を簡素化できるが、一文字送る毎に数ビットの制御データを付加しなければならないため伝送効率は悪く、高速通信には向かない。RS-232Cなどのシリアル通信方式でよく用いられる。

茶漉しに固形物の混ざった液体を注ぐと網目より大きな塊は濾し取られて小さなものは通過するように、何らかの基準や条件に基づいて通過させるかどうかを判断し、一部を通さない働きのことをこのように呼ぶ。そのような働きをする機器やソフトウェアは「フィルタ」(filter)という。

単にフィルタリングといった場合、パソコンやスマートフォンなどでインターネット上のWebページやオンラインサービスを利用する際、あらかじめ指定された条件に基づいて一部をアクセスできないよう制限する「コンテンツフィルタリング」(content filtering)機能のことを指すことが多い。主に保護者が未成年の子どもに好ましくないコンテンツやサービスに触れないようにするために用いられる。

メールフィルタリング

メールソフトやメールサーバなどが、受信したメールの内容や添付ファイルなどから迷惑メールやウイルスメールと疑わしいメールを選別し、専用のフォルダに集めたり破棄する機能を「メールフィルタリング」「スパムフィルタリング」などという。

パケットフィルタリング

インターネットとLAN(構内ネットワーク)の間などネットワーク境界に設置されたファイアウォールやルータなどが、内外を通過するデータ(パケット)を検査してウイルス感染や不正アクセスなどが疑われるものを破棄する機能を「パケットフィルタリング」という。

コンピュータでは、メモリ上でデジタルデータとして管理されている画面の表示情報をアナログ信号に変換してディスプレイ装置に送出したり、音声データをアナログ信号としてスピーカーに送出したりといった用途で主に用いられている。

アナログ信号を何段階のデジタル値で近似するかを分解能と呼び、ビット単位で表す。8ビットなら256段階、10ビットなら1024段階で波形を表現できる。また、1秒間に何回変換を行うことができるかをサンプリング速度(サンプリングレート/サンプリング周波数)と呼び、ヘルツ(Hz)単位で表す。1MHzなら毎秒100万回、1GHzなら10億回の変換を行う。

いずれの値も大きければ大きいほど元の波形に近い滑らかなアナログ信号を再現できる。ただし、両者はいずれかを向上させるともう一方の性能を高めるのが難しいトレードオフの関係にあるため、用途に応じてどちらを重視するか考えて方式や製品の選択などを行う必要がある。

D/A変換には原理が異なる複数の方式があり、得意な分野や用途が異なっている。よく知られるのは多数の抵抗を並べた抵抗ラダー型や抵抗ストリング型、キャパシタ(コンデンサ)を用いる容量アレイ型、オーバーサンプリングという手法を応用したΔΣ(デルタシグマ)型、電流の大きさを変化させて信号を出力する電流出力型などがある。

D/A変換とは逆に、アナログ信号をデジタル信号に変換する電子回路のことを「A/Dコンバータ」(ADC：デジタルアナログ変換器)という。電波や電気信号の受信、写真や映像の撮影、音声の録音など、自然界の物理状態をデジタル値の列に変換してコンピュータで利用するために必要となる。

単位時間あたりの標本化の回数をサンプリング周波数(サンプリングレート)と呼び、毎回の標本データを表現する値のビット数を量子化ビット数という。これらの値が大きいほどアナログ波形をより正確にデジタルデータの集合として記録できるが、単位時間あたりの記録に必要なデータ量は増大する。

音声や光(画像・映像)、電気信号、電波などを電子機器に取り込んでデジタル処理するためには、センサーやアンテナなどが得たアナログ信号をA/D変換でデジタルデータに変換する必要があり、様々な機器の内部に内蔵されている。

A/D変換とは逆に、デジタル信号を元にアナログ信号を生成する電子回路のことをDAC(D/Aコンバータ、デジタルアナログ変換器)という。

システムは入力に基づいて出力を決定するが、フィードバック制御では出力そのものや、出力によって生じた制御対象の変化などを測定し、入力として与える。出力の内容は直前の出力の結果を反映して変化する。この仕組みは機械などの制御システムだけでなく、生体メカニズムなどにも見られる。

例えば、ヒーターで対象物の温度を一定に保つ装置を制御する際、入力として対象物の温度の測定結果を与える。これにより、温度が規定を下回ったらヒーターの出力を上げ、規定を上回ったら一時停止するといった制御を行い、温度を一定に保つことができる。

一方、出力や結果を入力として用いずに、あらかじめ設定されたモデルに基づいて状態を予測して出力を決定する方式を「フィードフォワード制御」(feedforward control)という。検知可能な外乱による影響に対して、フィードバック制御はその影響が実際に出てからしか対処できないが、フィードフォワード制御は影響を事前に予測して先手を打つことができるため、フィードバック制御を補完するように組み合わせることが多い。

機械制御などの分野では、移動する機械を停止させる処理のように、処理の完了に期限が定められていることがある。そのような制約のある制御プログラムの実行に適した環境を提供するのがリアルタイムOSの役割である。

RTOSの特徴

組み込みシステムはパソコンやサーバなどに比べの非力なCPUやマイクロコントローラ、容量の少ないメインメモリで構成されることが多いため、リアルタイムOSもそれに合わせてプログラムサイズが極めてコンパクトに抑えられており、処理も高速で応答性に優れる。

一般的な汎用OSに見られない特徴として、最悪の場合の応答時間を保証し、一つ一つの処理の実行時間を予測可能にしている。複数のプログラムのマルチタスク(並行処理)は可能だが、優先度ベースのスケジューリング機構を備え、優先度が高く設定された処理を遅延なく実行できるよう制御する。

一方、汎用OSの多くに見られる仮想メモリなど実時間性を損なう機能は提供されない。パソコン向けOSなどでは標準的なネットワーク通信やグラフィック表示(GUI)などの基本的な機能も、オプションやモジュールとして取捨選択できるようになっており、ターゲット機器に不要であれば削除してその分軽量にすることができる。

RTOSの種類

リアルタイムシステムは機器の種類や内部の構成、必要な機能や要求事項が極めて多様であるため、リアルタイムOSもターゲットや得意分野によって多くの製品が提供されている。

よく知られる製品としてはVxWorks、eCos、LynxOS、QNX、μC/OS、FreeRTOS、ThreadX、Nucleus RTOSなどがある。日本ではTRONプロジェクトから派生したμITRON、T-Kernel、TOPPERS系統の製品も人気が高い。LinuxカーネルをRTOS化したRTLinuxやART-Linux、Windowsから派生したWindows CEやWindows Embeddedなど、汎用OSをベースとした製品もある。

組み込みシステムに導入されるOSは「組み込みOS」と総称されるが、リアルタイムOSはその一部であり、組み込み機器全体ではリアルタイム性のない組み込みOSの方が一般的である。Windows系やLinux系、Androidなどが該当し、店頭の注文端末やキオスク端末、ATM、デジタルサイネージ、デジタル家電などに採用されている。

コンピュータと関わりの深いセンサーとしては、音声を電気信号に変換するマイク(マイクロフォン)や、受光素子が受けた光を電気信号に変換するイメージセンサー、タッチパネルなどで画面への指先の接触を検知する接触センサー、家庭用ゲーム機のコントローラーなどで動きや回転を捉える加速度センサーやジャイロスコープなどがある。

小型のセンサー機器に外部との通信機能やICチップによる高度な情報処理機能を統合し、データの蓄積や変換など何らかの処理を行ったり、複数のセンサー素子の情報を統合したり、ITシステムや機器の制御システムと連携する機能を持ったものを「スマートセンサー」(smart sensor)という。

また、電源と無線通信機能を内蔵した小型のセンサー機器を分散して設置し、それら協調して動作させることで、施設や設備の監視・制御や、環境や空間の観測などを行なう通信ネットワークを「センサネットワーク」(WSN：Wireless Sensor Network)という。

最も一般的な動作原理はバネにつながれたおもりを用いる方法で、バネの伸び縮みする方向に加速度が生じるとその大きさに応じておもりに力が加わり位置が移動するため、これを計測してフックの法則から加速度を求める。

おもりの移動量を検知する方式の違いにより、光学式や機械式、半導体式(静電容量型やピエゾ抵抗型など)に分かれ、装置の小型化が可能な半導体式が主流となっている。バネを振動させ振動周波数の変化を計測する方式もある。

一つの加速度センサーが検知できる加速度の向きは一方向(一軸)であるため、空間上のあらゆる動きを検知するには三つの計測器を互いに垂直になるよう配置する必要がある。このような任意の動きに対応できる装置を三軸加速度センサーという。

加速度センサーはゲームコントローラーに内蔵してコントローラー自体を動かす操作の検知に利用されるほか、スマートフォンなどの携帯機器で重力加速度を計測して機器の傾きに応じて自動的に画面表示の向きを変更する制御、ロボットの姿勢制御、自動車のエアバッグの衝突検知など、様々な機器に応用される。

航空機や船舶、ロケット、人工衛星、カーナビゲーションシステム、スマートフォン、デジタルカメラ、ゲーム機のコントローラーなどに幅広く応用されている。「ジャイロセンサー」は和製英語で、英語では “gyroscope” (ジャイロスコープ)あるいは略して “gyro” (ジャイロ)という。

動作原理に応じて機械式や流体式、光学式などの種類があるが、よく知られているのは最初に発明された機械式で、球状の枠の内部に固定された円盤が回転する回転型ジャイロスコープが有名である。自転する物体に働く慣性力(ジャイロ効果)を利用する。精度は高いが装置が大掛かりなため主に大型の機械で用いられる。

スマートフォンなど小型の電子機器に内蔵される装置の場合には、小さな音叉や輪の形をした部品を振動させる振動型がよく用いられる。振動する物体を回転させた時に働くコリオリの力を検知する。

単純な構造の装置は特定の一つの軸の周りの回転しか検知できない1軸ジャイロスコープだが、構造を工夫したり複数の検知器を組み合わせることで、互いに直交する2軸や3軸の回転を検知できる装置もある。我々の住む世界の空間は3次元であるため、3軸型はあらゆる方向の回転を検知できる。

温度と抵抗変化の関係によりいくつかの種類に分類される。温度センサーなどで最も一般的に用いられるのは「NTCサーミスタ」(Negative Temperature Coefficient)で、温度の上昇に応じて緩やかに抵抗が減少する(温度が下降すると抵抗が増大する)。抵抗値を測定することで周囲の温度を知ることができる。

一方、閾値となる一定の温度を超えると急激に抵抗が増大するものを「PTCサーミスタ」(Positive Temperature Coefficient)という。装置や回路の過熱を防止する保護回路などとして用いられる。逆に、閾値を超えると急激に抵抗が減少するものを「CTRサーミスタ」(Critical Temperature Resistor)という。