第2章: 情報理論とバイナリ通信
2.1 Claude Shannon と情報理論の誕生
2.1.1 "A Mathematical Theory of Communication" (1948)
1948年、Bell Labsの数学者 Claude Shannon は、論文 "A Mathematical Theory of Communication" を発表し、デジタル通信の数学的基礎を確立しました。この論文は、コンピュータ科学史上最も重要な論文の一つとされています。
> "The fundamental problem of communication is that of reproducing at one point either exactly or approximately a message selected at another point." > — Claude Shannon, 1948
Shannon が解決した問題：
【通信の本質的問題】
送信者 ─────→ 通信路 ─────→ 受信者
M ↓ M'
ノイズ
問題: M' = M となることをどう保証するか？
Shannon の洞察:
1. すべてのメッセージは「情報」として数学的に扱える
2. 情報は「ビット」で測定できる
3. 通信路には「容量」がある
4. 適切な符号化で信頼性を高められる
2.1.2 情報エントロピーの定義
Shannon は「情報量」を数学的に定義しました：
定義: 情報エントロピー H
確率 p のイベントが持つ情報量:
I(p) = -log₂(p) ビット
情報源 S = {s₁, s₂, ..., sₙ} のエントロピー:
H(S) = -Σ p(sᵢ) log₂ p(sᵢ)
例: 公平なコイン投げ
p(表) = p(裏) = 0.5
H = -[0.5 × log₂(0.5) + 0.5 × log₂(0.5)]
= -[0.5 × (-1) + 0.5 × (-1)]
= 1 ビット
例: 偏ったコイン (p(表) = 0.9, p(裏) = 0.1)
H = -[0.9 × log₂(0.9) + 0.1 × log₂(0.1)]
≈ 0.47 ビット
Minitalkへの示唆：
SIGUSR1 と SIGUSR2 は等確率で使用される
→ 1シグナルあたり 1ビット の情報を伝達可能
→ これは情報理論的に最適な符号化
2.1.3 シリアル通信の理論
通信は大きく「並列」と「直列（シリアル）」に分類されます：
【並列通信】
┌─── ビット7 ───┐
├─── ビット6 ───┤
├─── ビット5 ───┤
送信側 ─┼─── ビット4 ───┼─ 受信側
├─── ビット3 ───┤
├─── ビット2 ───┤
├─── ビット1 ───┤
└─── ビット0 ───┘
→ 高速だが、多数の通信線が必要
【シリアル通信】
送信側 ─────────────────────────────── 受信側
b7 → b6 → b5 → b4 → b3 → b2 → b1 → b0
←──────── 時間 ──────────→
→ 1本の通信線で済むが、低速
Minitalkはシリアル通信:
- 通信「線」= シグナル
- 8ビットを順番に送信
- 1文字 = 8回のシグナル送信
2.2 ビットとバイトの数学的基礎
2.2.1 位取り記数法（Positional Notation）
私たちが日常使う10進法と、コンピュータが使う2進法は、どちらも「位取り記数法」に基づいています：
位取り記数法の一般形:
N = Σ aᵢ × bⁱ (i = 0, 1, 2, ...)
N : 表現される数
b : 基数（base）
aᵢ: 位 i の係数（0 ≤ aᵢ < b）
10進法（b = 10）:
254 = 2×10² + 5×10¹ + 4×10⁰
= 200 + 50 + 4
2進法（b = 2）:
11111110 = 1×2⁷ + 1×2⁶ + 1×2⁵ + 1×2⁴ + 1×2³ + 1×2² + 1×2¹ + 0×2⁰
= 128 + 64 + 32 + 16 + 8 + 4 + 2 + 0
= 254
なぜコンピュータは2進法を使うのか：
- 物理的単純さ: 電圧の高低（ON/OFF）で表現できる
- ノイズ耐性: 2状態なら判別が容易
- 論理演算との親和性: AND, OR, NOT が直接実装可能
2.2.2 ビット位置と重み
1バイト（8ビット）の各位置には「重み」があります：
ビット位置: 7 6 5 4 3 2 1 0
重み（2進）: 2⁷ 2⁶ 2⁵ 2⁴ 2³ 2² 2¹ 2⁰
重み（10進）: 128 64 32 16 8 4 2 1
例: 'A' の ASCII コード 65
ビット: 0 1 0 0 0 0 0 1
重み: 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1
計算: 0 + 64 + 0 + 0 + 0 + 0 + 0 + 1 = 65
MSB (Most Significant Bit) = ビット7 (最上位ビット)
LSB (Least Significant Bit) = ビット0 (最下位ビット)
2.2.3 バイトオーダー（エンディアン）
複数バイトのデータを格納・送信する際、バイトの順序が問題になります：
【エンディアン問題】
32ビット整数 0x12345678 をメモリに格納:
ビッグエンディアン（Big-Endian）:
アドレス: 0x00 0x01 0x02 0x03
内容: 0x12 0x34 0x56 0x78
（上位バイトが低いアドレスに）
採用: ネットワーク、Motorola 68k、SPARC
リトルエンディアン（Little-Endian）:
アドレス: 0x00 0x01 0x02 0x03
内容: 0x78 0x56 0x34 0x12
（下位バイトが低いアドレスに）
採用: x86, x64, ARM (通常)
語源: Jonathan Swift の『ガリヴァー旅行記』
卵の割り方をめぐるリリパット国の争い
Minitalkにおけるバイトオーダー：
Minitalk では1バイトずつ送信するため、
バイトオーダーは問題にならない。
ただし、ビット送信順序は統一が必要:
- MSB first: 人間が読みやすい（一般的）
- LSB first: 一部のプロトコルで使用
2.3 ASCII - 文字符号化の標準
2.3.1 ASCII の歴史（1963年）
ASCII（American Standard Code for Information Interchange）は、1963年にASA（American Standards Association、現ANSI）によって制定されました。
ASCII 以前の問題：
1960年代初頭の状況:
- IBM: EBCDIC
- Teletype: Baudot code
- その他多数の独自コード
問題: 異なるシステム間でテキストを共有できない！
解決: 標準化された文字コードの制定 → ASCII
ASCII の設計思想：
2.3.2 ASCII コード表
【ASCII コード表（抜粋）】
Dec Hex Char Dec Hex Char Dec Hex Char
─────────────────────────────────────────────────
0 00 NUL 32 20 SP 64 40 @
1 01 SOH 33 21 ! 65 41 A
2 02 STX 34 22 " 66 42 B
7 07 BEL 48 30 0 90 5A Z
8 08 BS 49 31 1 97 61 a
9 09 HT 50 32 2 122 7A z
10 0A LF 57 39 9 127 7F DEL
13 0D CR
重要な特徴:
- '0'-'9' は連続（48-57）: 数字 - '0' で数値に変換可能
- 'A'-'Z' は連続（65-90）: 大文字
- 'a'-'z' は連続（97-122）: 小文字
- 大文字と小文字の差は32（ビット5が異なる）
2.3.3 制御文字の意味
ASCII の最初の32文字は「制御文字」です：
【重要な制御文字】
Dec Name 意味 Minitalkでの扱い
────────────────────────────────────────────────────
0 NUL Null（文字列終端） メッセージ終了の検出
10 LF Line Feed（改行） そのまま出力
13 CR Carriage Return そのまま出力
27 ESC Escape エスケープシーケンス開始
127 DEL Delete 通常の文字として扱う
Minitalk では:
- NUL (0x00) を受信 → メッセージ終了
- その他の制御文字 → write() でそのまま出力
2.4 ビット操作の代数
2.4.1 ブール代数の基礎
George Boole が1854年に確立した「ブール代数」は、ビット操作の数学的基盤です：
【ブール代数の基本演算】
NOT (否定):
¬0 = 1
¬1 = 0
AND (論理積):
0 ∧ 0 = 0
0 ∧ 1 = 0
1 ∧ 0 = 0
1 ∧ 1 = 1
OR (論理和):
0 ∨ 0 = 0
0 ∨ 1 = 1
1 ∨ 0 = 1
1 ∨ 1 = 1
XOR (排他的論理和):
0 ⊕ 0 = 0
0 ⊕ 1 = 1
1 ⊕ 0 = 1
1 ⊕ 1 = 0
【代数法則】
結合律: (A ∧ B) ∧ C = A ∧ (B ∧ C)
交換律: A ∧ B = B ∧ A
分配律: A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)
ド・モルガンの法則: ¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
2.4.2 C言語のビット演算子
ブール代数は C言語では以下の演算子で表現されます：
/*
* C言語のビット演算子
*/
/* NOT (ビット反転) */
~x
/* AND */
x & y
/* OR */
x | y
/* XOR */
x ^ y
/* 左シフト */
x << n /* x を n ビット左へ */
/* 右シフト */
x >> n /* x を n ビット右へ */
/* 具体例 */
unsigned char a = 0b11001010; // 202
unsigned char b = 0b10101100; // 172
~a = 0b00110101 // 53 (8ビットの場合)
a & b = 0b10001000 // 136
a | b = 0b11101110 // 238
a ^ b = 0b01100110 // 102
a << 2 = 0b00101000 // 40 (上位2ビットは消失)
a >> 2 = 0b00110010 // 50
2.4.3 ビットマスクのテクニック
特定のビットを操作するための基本パターン：
/*
* ビット操作の基本パターン
*/
/* 1. 特定ビットの取得（読み取り） */
int get_bit(unsigned char byte, int pos)
{
return (byte >> pos) & 1;
/*
* 例: byte = 0b01000001, pos = 6
* byte >> 6 = 0b00000001
* & 1 = 0b00000001 = 1
*/
}
/* 2. 特定ビットを1にセット */
void set_bit(unsigned char *byte, int pos)
{
*byte |= (1 << pos);
/*
* 例: byte = 0b00000001, pos = 6
* 1 << 6 = 0b01000000
* |= → 0b01000001
*/
}
/* 3. 特定ビットを0にクリア */
void clear_bit(unsigned char *byte, int pos)
{
*byte &= ~(1 << pos);
/*
* 例: byte = 0b01000001, pos = 0
* 1 << 0 = 0b00000001
* ~ = 0b11111110
* &= → 0b01000000
*/
}
/* 4. 特定ビットを反転（トグル） */
void toggle_bit(unsigned char *byte, int pos)
{
*byte ^= (1 << pos);
}
/* 5. 複数ビットの抽出 */
unsigned char extract_bits(unsigned char byte, int start, int len)
{
unsigned char mask = (1 << len) - 1;
return (byte >> start) & mask;
/*
* 例: byte = 0b11010110, start = 2, len = 3
* mask = 0b00000111
* byte >> 2 = 0b00110101
* & mask = 0b00000101 = 5
*/
}
2.5 ビットシリアライゼーション
2.5.1 シリアライゼーションの概念
「シリアライゼーション」（serialization）とは、データ構造を連続したバイト列に変換する処理です：
【シリアライゼーションの一般概念】
メモリ上のデータ構造 シリアライズ バイト列
┌─────────────┐ ─────────→ ┌─────────────┐
│ struct { │ │ byte 0 │
│ int x; │ │ byte 1 │
│ char y; │ │ byte 2 │
│ ... │ │ ... │
│ } │ │ byte n │
└─────────────┘ ←───────── └─────────────┘
デシリアライズ
Minitalkでのビットシリアライゼーション:
文字 'A' ビット列 シグナル列
┌─────┐ ┌─────────┐ ┌────────────────┐
│ 65 │ ──────→ │01000001 │ ───→ │U1 U2 U1 U1 U1 │
└─────┘ └─────────┘ │U1 U1 U2 │
└────────────────┘
2.5.2 MSB First シリアライゼーション
最上位ビットから順に送信する方法（Minitalkで一般的）：
/*
* MSB (Most Significant Bit) First
* 人間が読みやすい順序
*/
void send_char_msb(pid_t pid, unsigned char c)
{
int bit_pos;
bit_pos = 7; /* 最上位ビットから開始 */
while (bit_pos >= 0)
{
/* ビット位置を右シフトして最下位に持ってくる */
if ((c >> bit_pos) & 1)
kill(pid, SIGUSR2); /* 1 */
else
kill(pid, SIGUSR1); /* 0 */
usleep(100);
bit_pos--;
}
}
/*
* 送信例: 'A' = 65 = 0b01000001
*
* bit_pos=7: c >> 7 = 0b0, & 1 = 0 → SIGUSR1
* bit_pos=6: c >> 6 = 0b01, & 1 = 1 → SIGUSR2
* bit_pos=5: c >> 5 = 0b010, & 1 = 0 → SIGUSR1
* bit_pos=4: c >> 4 = 0b0100, & 1 = 0 → SIGUSR1
* bit_pos=3: c >> 3 = 0b01000, & 1 = 0 → SIGUSR1
* bit_pos=2: c >> 2 = 0b010000, & 1 = 0 → SIGUSR1
* bit_pos=1: c >> 1 = 0b0100000, & 1 = 0 → SIGUSR1
* bit_pos=0: c >> 0 = 0b01000001, & 1 = 1 → SIGUSR2
*
* 送信順: U1, U2, U1, U1, U1, U1, U1, U2
*/
2.5.3 MSB First デシリアライゼーション
受信側でビットを再構成する方法：
/*
* MSB First 受信
* 左シフトしながらビットを追加
*/
static unsigned char g_char = 0;
static int g_bit_count = 0;
void receive_bit_msb(int signum)
{
/* 既存のビットを左にシフト（次のビットの場所を作る） */
g_char <<= 1;
/* 受信したビットを最下位に追加 */
if (signum == SIGUSR2)
g_char |= 1;
g_bit_count++;
if (g_bit_count == 8)
{
write(1, &g_char, 1);
g_char = 0;
g_bit_count = 0;
}
}
/*
* 受信例: 'A' の復元
*
* 初期: g_char = 0b00000000
*
* 受信1 (U1=0): 0b00000000 << 1 = 0b00000000, |= 0 → 0b00000000
* 受信2 (U2=1): 0b00000000 << 1 = 0b00000000, |= 1 → 0b00000001
* 受信3 (U1=0): 0b00000001 << 1 = 0b00000010, |= 0 → 0b00000010
* 受信4 (U1=0): 0b00000010 << 1 = 0b00000100, |= 0 → 0b00000100
* 受信5 (U1=0): 0b00000100 << 1 = 0b00001000, |= 0 → 0b00001000
* 受信6 (U1=0): 0b00001000 << 1 = 0b00010000, |= 0 → 0b00010000
* 受信7 (U1=0): 0b00010000 << 1 = 0b00100000, |= 0 → 0b00100000
* 受信8 (U2=1): 0b00100000 << 1 = 0b01000000, |= 1 → 0b01000001
*
* 結果: 0b01000001 = 65 = 'A'
*/
2.5.4 LSB First の場合
比較のため、LSB First も説明します（一部のプロトコルで使用）：
/*
* LSB (Least Significant Bit) First
* 一部のハードウェアプロトコルで使用
*/
/* 送信 */
void send_char_lsb(pid_t pid, unsigned char c)
{
int bit_pos;
bit_pos = 0; /* 最下位ビットから開始 */
while (bit_pos < 8)
{
if ((c >> bit_pos) & 1)
kill(pid, SIGUSR2);
else
kill(pid, SIGUSR1);
usleep(100);
bit_pos++;
}
}
/* 受信 */
void receive_bit_lsb(int signum)
{
/* 受信したビットを現在の位置にセット */
if (signum == SIGUSR2)
g_char |= (1 << g_bit_count);
g_bit_count++;
if (g_bit_count == 8)
{
write(1, &g_char, 1);
g_char = 0;
g_bit_count = 0;
}
}
/*
* 注意: 送信側と受信側で同じ方式を使う必要がある！
*/
2.6 文字列の送信プロトコル
2.6.1 プロトコル設計の考慮事項
文字列全体を送信するには、追加の考慮が必要です：
【文字列送信の問題】
問題1: 文字列の終端をどう知らせるか？
→ 方法A: 長さを先に送信
→ 方法B: 終端文字（NUL）を送信 ← Minitalkで使用
問題2: エラー検出・訂正は必要か？
→ Minitalkでは通常不要（短距離、同一マシン）
→ ボーナスでチェックサム追加も可能
問題3: 複数クライアントへの対応は？
→ 基本: 1クライアントのみ
→ ボーナス: 複数クライアント対応
2.6.2 Minitalk の基本プロトコル
【Minitalk 基本プロトコル】
┌───────────────────────────────────────────────────────────┐
│ メッセージフレーム │
├───────────────────────────────────────────────────────────┤
│ [文字1] [文字2] [文字3] ... [文字n] [NUL] │
│ 8bit 8bit 8bit 8bit 8bit │
└───────────────────────────────────────────────────────────┘
各文字は8つのシグナルで構成:
SIGUSR1 = ビット0
SIGUSR2 = ビット1
終端:
NUL文字（0x00）を受信したらメッセージ終了
例: "Hi" を送信
'H' = 0x48 = 0b01001000 → U1 U2 U1 U1 U2 U1 U1 U1
'i' = 0x69 = 0b01101001 → U1 U2 U2 U1 U2 U1 U1 U2
NUL = 0x00 = 0b00000000 → U1 U1 U1 U1 U1 U1 U1 U1
2.6.3 文字列送信の実装
/*
* 完全な文字列送信関数
*/
void send_string(pid_t server_pid, const char *str)
{
while (*str)
{
send_char_msb(server_pid, (unsigned char)*str);
str++;
}
/* 終端の NUL を送信 */
send_char_msb(server_pid, '\0');
}
/*
* クライアントのmain関数
*/
int main(int argc, char **argv)
{
pid_t server_pid;
if (argc != 3)
{
write(2, "Usage: ./client <server_pid> <message>\n", 39);
return (1);
}
server_pid = ft_atoi(argv[1]);
if (server_pid <= 0)
{
write(2, "Error: Invalid PID\n", 19);
return (1);
}
send_string(server_pid, argv[2]);
return (0);
}
2.7 SIGUSR1 と SIGUSR2 の選択理由
2.7.1 ユーザー定義シグナルの意義
なぜ Minitalk は SIGUSR1 と SIGUSR2 を使うのでしょうか？
【シグナルの分類】
1. システム予約シグナル（使用不可）
SIGKILL (9) - 強制終了（キャッチ不可）
SIGSTOP (19) - 停止（キャッチ不可）
2. イベント通知シグナル（OS が使用）
SIGINT (2) - Ctrl+C
SIGTERM (15) - 終了要求
SIGCHLD (17) - 子プロセス状態変化
3. エラー通知シグナル（OS が使用）
SIGSEGV (11) - セグメンテーション違反
SIGFPE (8) - 浮動小数点例外
4. ユーザー定義シグナル（自由に使用可能）
SIGUSR1 (10) - ユーザー定義1
SIGUSR2 (12) - ユーザー定義2
Minitalkで SIGUSR1/2 を使う理由:
- OSと干渉しない
- 他のプログラムと競合しにくい
- 2つあるので2進数の0/1を表現できる
2.7.2 シグナル番号の確認
実際のシグナル番号はシステムによって異なる場合があります：
#include <signal.h>
#include <stdio.h>
int main(void)
{
printf("SIGUSR1 = %d\n", SIGUSR1);
printf("SIGUSR2 = %d\n", SIGUSR2);
return (0);
}
/*
* 典型的な出力:
*
* Linux x86_64:
* SIGUSR1 = 10
* SIGUSR2 = 12
*
* macOS:
* SIGUSR1 = 30
* SIGUSR2 = 31
*
* → マジックナンバーではなく、
* 必ずシンボル(SIGUSR1/SIGUSR2)を使うこと！
*/
2.7.3 シグナルの一意性保証
SIGUSR1 と SIGUSR2 は「キューイングされない」という特性があります：
【キューイングの問題】
同じシグナルが連続で送られた場合:
送信: SIGUSR1 → SIGUSR1 → SIGUSR1
↓
受信: SIGUSR1 (1回だけ)
理由: 標準シグナルは「ビットマスク」で管理されるため、
同じシグナルは1つしか保留できない
対策:
1. 十分な待機時間（usleep）を設ける
2. ACKメカニズムで確実に受信を確認（ボーナス）
2.8 信頼性と同期
2.8.1 シグナルロスの数学的分析
シグナルロスの確率を分析してみましょう：
【シグナルロスのモデル】
仮定:
- シグナル処理時間: T_h マイクロ秒
- シグナル送信間隔: T_s マイクロ秒
シグナルロスの条件:
T_s < T_h の場合、ロストの可能性あり
例:
T_h = 50 μs（ハンドラ処理時間）
T_s = 30 μs（送信間隔）
→ シグナルロストの可能性が高い
安全な設定:
T_s > T_h + マージン
例: T_s = 100 μs（T_h の2倍以上）
2.8.2 適切な待機時間の決定
/*
* 待機時間の経験則
*/
/* 短すぎる（危険） */
#define DELAY_DANGEROUS 10 /* μs - ロスト頻発 */
/* 最小限（リスクあり） */
#define DELAY_MINIMUM 50 /* μs - 負荷が高いとロスト */
/* 推奨（安全） */
#define DELAY_SAFE 100 /* μs - 通常はこれで十分 */
/* 確実（低速） */
#define DELAY_RELIABLE 500 /* μs - ほぼ確実だが遅い */
/*
* 送信速度の計算:
*
* DELAY = 100 μs の場合:
* 1文字 = 8ビット × 100μs = 800μs = 0.8ms
* 1秒で送れる文字数 = 1,000,000 / 800 = 1,250 文字
* → 約1.2KB/秒
*
* 参考: 現代のネットワークは GB/秒のオーダー
* シグナル通信は極めて低速
*/
2.8.3 ACKメカニズム（ボーナス用）
より確実な通信のための確認応答メカニズム：
/*
* ACK (Acknowledgment) プロトコル
*
* 動作:
* 1. クライアント: ビットを送信
* 2. サーバー: 受信したらACKを返信
* 3. クライアント: ACKを受け取ったら次のビットを送信
*/
/* クライアント側 */
volatile sig_atomic_t g_ack = 0;
void ack_handler(int sig)
{
(void)sig;
g_ack = 1;
}
int send_bit_reliable(pid_t pid, int bit)
{
int timeout;
g_ack = 0;
if (bit)
kill(pid, SIGUSR2);
else
kill(pid, SIGUSR1);
/* ACKを待つ（タイムアウト付き） */
timeout = 1000; /* 最大1000回 × 10μs = 10ms */
while (!g_ack && timeout > 0)
{
usleep(10);
timeout--;
}
return (g_ack);
}
/* サーバー側 */
void handler_with_ack(int sig, siginfo_t *info, void *ctx)
{
(void)ctx;
/* ビット処理 */
g_char <<= 1;
if (sig == SIGUSR2)
g_char |= 1;
g_bit_count++;
/* ACKを送信 */
kill(info->si_pid, SIGUSR1);
if (g_bit_count == 8)
{
write(1, &g_char, 1);
g_char = 0;
g_bit_count = 0;
}
}
2.9 まとめ
この章では、Minitalkの通信基盤となる理論を学びました：
学んだこと
- 位取り記数法とビット
- ASCII 文字コード（1963年）
- ブール代数とビット操作
- シリアライゼーション
- 信頼性と同期
次章の予告
第3章では、シグナルハンドラと sigaction() について学びます：
- sigaction() の詳細な使い方
- SA_SIGINFO フラグと siginfo_t 構造体
- シグナルマスクの活用
- 堅牢なサーバー実装
---
参考文献：
- Shannon, C. E. (1948). "A Mathematical Theory of Communication". Bell System Technical Journal, 27(3), 379-423.
- Boole, G. (1854). An Investigation of the Laws of Thought. Walton and Maberly.
- American National Standards Institute. (1963). ASCII - American Standard Code for Information Interchange. ANSI X3.4.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd ed.). Prentice Hall.