教養としてのコンピューターサイエンス講義 今こそ知っておくべき「デジタル世界」の基礎知識

  • グラフの音圧の波の高さ(縦軸)は、音の強度または大きさを表しています。横軸は時間を表し、1秒あたりの波の数がピッチまたは周波数を表しています。
  • ここで私たちが、音の波の高さ(たとえばマイクからの音圧)を、一定時間ごとに測定したとします。これらの測定値は、元の曲線を近似する一連の数値を提供します。より頻繁に、そしてより正確に測定すればするほど、近似値はより正確になります。結果として得られる数値の列は、保存したりコピーしたり、あるいは操作したり他の場所へ送ったりできる、波形のデジタル表現なのです。数値列を、対応する電圧または電流のパターンに変換し、スピーカーまたはイヤフォンを駆動して音に戻す機器を用いて、再生できるのです。波形から数値列への変換はアナログ/デジタル変換と呼ばれ、これを行うデバイスは A/Dコンバーターと呼ばれます。逆向きは、もちろん、デジタル/アナログ変換または D/A と呼ばれます。変換は決して完璧ではなく、それぞれの方向で何かが失われていきます。ほとんどの人にとって、この劣化は知覚できないものですが、オーディオマニアたちはそれができると主張しています。
  • なぜ 10 進数の代わりに2進数を使うのでしょう?その答えは簡単で、2つの状態(たとえばオンとオフ)だけを持つデバイスを作る方が、10 個の状態を持つデバイスを作るよりも、はるかに簡単だからです。この比較的単純な性質は、様々な技術を使って表現することができます。たとえば、電流(流れているか否か)、電圧(高いか低いか)、電荷(存在しているか否か)、磁気(北または南)、光(明暗)、反射率(輝いているか鈍いか)などを使えるのです。フォン・ノイマンはこのことをはっきりと認識していました。1946年に彼は、「私たちの基本的な記憶単位は、もちろん2進数を応用したものになります。なぜならその変化の度合いを測定したくないからです」と述べています。

 

  • 残念なことですが、本格的なプログラムが最初から動くことはありません。人生はとても複雑で、プログラムはその複雑さを反映しているのです。プログラミングは、わずかな人しか持ち合わせていない、細部への完璧な注意を必要とするのです。したがって、あらゆる規模のすべてのプログラムには、エラーが含まれています。つまり、ある状況下において、プログラムは間違ったことをしたり、間違った答えを生み出したりするのです。こうした欠陥は「バグ」と呼ばれています。 
  • プログラマーというものは、詩人と同じように、純粋な思考からわずかに取り出されたものを相手に仕事をしています。
    彼は想像力を行使して創造を行い、空気の中から空中へと、
    自らの城を作り出すのです。これほど柔軟で、洗練とやり直しが容易で、かつ壮大な概念構造を簡単に実現できる創造的メディアは多くありません、フレデリックブルックス、The Mythical Man-Month、人月の神話、1975
  • 文学作品『高慢と偏見』(Pride and Prejudice)は英語で 97,000 ワード、もしくは550,000 バイトをいくらか超える大きさです。最も出現頻度の高い文字は、実は単語間のスペースです。作品には91,000個以上のスペースが含まれています。
    次に最も頻度の高い文字は、e (55,100回)、t (36,900 回)、そしてa (33,200回)です。一方、Zの出現は3回、Xは1回だけです。最も頻度の低い小文字は、jが469 回、qが509 回、そしてzとxがそれぞれ約 700 回です。
  • 明らかにスペース、e、t、そしてaにそれぞれ2ビットを使用すれば、データを大幅に節約できます。そして、X、Z、およびその他の頻度の低い文字に、8ビット以上を使用しなければならなかったとしても問題ではありません。ハフマン符号化(Huffman coding)と呼ばれるアルゴリズムは、これを体系的に行い、個々の文字をエンコードできる可能な限り最適な圧縮を見つけます。このアルゴリズムを使うと『高慢と偏見』は44%圧縮され、その大きさは310,000 バイトになります、つまり平均すると1文字あたり4ビットしか使っていないということになります。
  • たとえば、単語全体やフレーズ全体など、単一の文字よりも大きな塊を圧縮し、ソースドキュメントの特性に適合させることで、さらに圧縮を改善できます。いくつかのアルゴリズムがこれを上手に行います。広く使用されている Zip プログラムは、例題の本を64パーセント圧縮し、202,000 バイトの大きさにします。bzip 2と呼ばれる Unixプログラムは、原文を 145,000 バイトに圧縮します、元のサイズのわずか4分の1ということです。
  • これらの技術はすべてロスレス圧縮を行います。この圧縮では情報が失われないため、圧縮を解除するとオリジナルの情報が正確に復元されます。直観に反するように思えるかもしれませんが、元の入力を正確に再現する必要がない場合もあります、つまり近似バージョンで十分だということです。そして、そうした状況では、ロッシー(非可逆)圧縮技術を使うことでさらに良い圧縮を行うことができます。
  • ロッシー圧縮は、人びとが見たり聞いたりするコンテンツに最もよく使用されます。デジタルカメラの画像を圧縮することを考えてみてください。人間の目は、互いに非常に似通った色を区別できないため、入力の正確な色を保持する必要はありません。より少ない色で十分ですし、より少ないビットでエンコードできます。同様に、細かい部分を捨ててしまうこともできます。結果の画像は元の画像ほど鮮明ではありませんが、人間の目では気が付きません。明るさの細かいグラデーションにも同じことが言えます。
  • 広く使われている、ファイル拡張子が.jpgの画像を生成する
    JPEG アルゴリズムは、この手法を用いて、目に見えるほどの劣化なしに、一般的な画像を10分の1以下の大きさに圧縮します。JPEGを生成するほとんどのプログラムは、圧縮率をある程度制御することができます。そうした場合の「高品質」とは、圧縮率が低いということを意味しています。
  • 同様の考えから、映画やテレビを圧縮するための MPEG ファミリーのアルゴリズムが生まれました。個々のフレームは JPEGのように圧縮されますが、さらに、あるフレームから次のフレームにかけてあまり変化しない一連の部分を圧縮することができるのです。また、動きの結果を予測し、変化のみをエンコードすることも可能です。さらに、動いている前景を静的な背景から分離して、後者のビット数を少なくすることもできます。
  • MP3とその後継の AAC は、MPEG の音声部分です。それらは、音を圧縮するための知覚を利用したコーディングアルゴリズムです。中でも、大きな音は柔らかい音を覆い隠し、人間の耳は約 20KHz を超える周波数を聞くことができない(年をとるにつれてその周波数は低くなっていきます)という事実が利用されています。このエンコードによって、標準の CD オーディオは約10分の1に圧縮されます。
  • 携帯電話は、人間の声に焦点を当てた大幅な圧縮を行っています。人間の声は、任意の音よりも大幅に圧縮できます。なぜなら、声は狭い周波数に収まっていますし、個別の話者ごとにモデル化できる声道から生まれているからです。個人の特徴を使うことによってより良い圧縮が可能になります。
  • あらゆる形式の圧縮における基本的な考え方は、情報内容を完全に伝えていないビットを削減もしくは排除すること、頻度の高い情報をより少ないビットでエンコーディングすること、頻繁に出現するシーケンスの辞書を作ること、そして繰り返しを回数でエンコーディングすることです。ロスレス圧縮では、オリジナルを完全に再構築できます。ロッシー圧縮では、受信者が必要としない一部の情報が破棄されます。これは、品質と圧縮率のトレードオフになります。

 

  •  圧縮が冗長な情報を削除するプロセスだとすると、エラーの検出と修正は、慎重に制御された冗長性を追加するプロセスです。冗長性があることで、エラーの検出や修正さえもが可能になるのです。
  • 一部の「共通番号」は、冗長性を備えていないので、エラーが発生してもそれを検出することができません。たとえば、米国の社会保障番号(SSN: Social Security Number)は9桁の数字ですが、ほとんどすべての9桁の並びが有効な番号になり得ます(これは誰かが、本当は不要なのにあなたの番号を聞いてきたときに役立ちます。適当に答えてしまえばよいからです)。しかし、いくつかの余分な数字が追加されていたり、またはいくつかの可能な値が除外されていた場合には、エラーを検出することが可能になります。
  • クレジットカードとキャッシュカードの番号は 16 桁ですが、16桁のすべての番号が有効なカード番号ではありません。それらの番号では、1954 年にIBM のピーター・ルーンが発明したチェックサムアルゴリズムを使用して、1桁のエラーと、多くの2桁が入れ替わる転置エラーを検出しています。これらは、実際に最もよく発生する種類のエラーなのです。
  • そのアルゴリズムは簡単です。右端の桁から開始し、連続する各桁に交互に1または2を掛け算します。結果が9より大きい場合は、9を引きます。結果の各数字を足していきます。こうして求まった合計は10で割り切れる必要があります。ご自分のカードと、4417 1234 56789112 の両方で確認してみてください。後者は一部の銀行が広告で使用している番号です。後者を計算してみるとその結果は9なので、これは有効な数字ではありません。しかし最後の桁を3に変更すると有効なものになります。
  • 書籍についている10桁または13桁の ISBN もまた、同様のアルゴリズムを利用して、似たような種類のエラーを防ぐチェックサムを持っています。バーコードや米国 POSTNET コード(郵便物の配送を補助するために米国郵便公社が利用しているコード)もチェックサムを使用しています。