第4章: ブール代数から文字エンコーディングへ

4.1 George Boole と論理代数の誕生(1854年)

4.1.1 「思考の法則」の数学化

1854年、アイルランドの数学者 George Boole は、画期的な著書 "An Investigation of the Laws of Thought"(思考の法則の研究)を発表しました。この著作は、人間の論理的思考を数学的に記述することを目指したものでした。

> "The design of the following treatise is to investigate the fundamental laws of those operations of the mind by which reasoning is performed." > — George Boole, 1854

Boole の革命的洞察:

【従来の論理学(アリストテレス以来)】

命題: 「すべてのAはBである」
      「あるAはBでない」

→ 言葉による推論

【Boole の数学的アプローチ】

x = 1 : 命題 x は真
x = 0 : 命題 x は偽

論理演算:
  x · y  : x かつ y (AND)
  x + y  : x または y (OR)
  1 - x  : x でない (NOT)

→ 代数的な計算で論理を扱える!

4.1.2 ブール代数の公理系

Boole の代数は、以下の公理に基づいています:

【ブール代数の公理】

1. 恒等律(Identity Laws)
   a ∨ 0 = a
   a ∧ 1 = a

2. 支配律(Domination Laws)
   a ∨ 1 = 1
   a ∧ 0 = 0

3. べき等律(Idempotent Laws)
   a ∨ a = a
   a ∧ a = a

4. 補元律(Complement Laws)
   a ∨ ¬a = 1
   a ∧ ¬a = 0

5. 交換律(Commutative Laws)
   a ∨ b = b ∨ a
   a ∧ b = b ∧ a

6. 結合律(Associative Laws)
   (a ∨ b) ∨ c = a ∨ (b ∨ c)
   (a ∧ b) ∧ c = a ∧ (b ∧ c)

7. 分配律(Distributive Laws)
   a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
   a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c)

8. 吸収律(Absorption Laws)
   a ∨ (a ∧ b) = a
   a ∧ (a ∨ b) = a

9. ド・モルガンの法則(De Morgan's Laws)
   ¬(a ∨ b) = ¬a ∧ ¬b
   ¬(a ∧ b) = ¬a ∨ ¬b

4.1.3 Claude Shannon とスイッチング回路(1937年)

約80年後、MIT大学院生の Claude Shannon は、修士論文 "A Symbolic Analysis of Relay and Switching Circuits"(1937年)で、ブール代数が電気回路の設計に直接適用できることを示しました。

> "It is possible to perform complex mathematical operations using only two states: on and off." > — Claude Shannon, 1937

Shannon の洞察:

【電気スイッチとブール代数の対応】

スイッチ ON  → 1(真)
スイッチ OFF → 0(偽)

直列接続(AND):
  ──[A]──[B]── : 両方 ON のときのみ電流が流れる
                A ∧ B = 1 ⟺ A = 1 かつ B = 1

並列接続(OR):
      ┌──[A]──┐
  ────┤       ├──── : どちらか ON なら電流が流れる
      └──[B]──┘
                A ∨ B = 1 ⟺ A = 1 または B = 1

→ デジタルコンピュータの理論的基盤!

4.2 ビット演算の代数的基礎

4.2.1 基本論理演算の真理値表

C言語のビット演算子は、ブール代数の演算に直接対応します:

【AND演算(&)】
 A | B | A & B
───┼───┼──────
 0 | 0 |   0
 0 | 1 |   0
 1 | 0 |   0
 1 | 1 |   1

用途: ビットマスク(特定ビットの抽出)


【OR演算(|)】
 A | B | A | B
───┼───┼──────
 0 | 0 |   0
 0 | 1 |   1
 1 | 0 |   1
 1 | 1 |   1

用途: ビットセット(特定ビットを1に)


【XOR演算(^)】
 A | B | A ^ B
───┼───┼──────
 0 | 0 |   0
 0 | 1 |   1
 1 | 0 |   1
 1 | 1 |   0

用途: ビットトグル、暗号化
特性: A ^ A = 0, A ^ 0 = A


【NOT演算(~)】
 A | ~A
───┼────
 0 |  1
 1 |  0

用途: ビット反転、マスクの生成

4.2.2 C言語でのビット演算

/*
 * ブール代数とC言語の対応
 */

#include <stdio.h>

void demonstrate_boolean_algebra(void)
{
    unsigned char a = 0b11001010;  /* 202 */
    unsigned char b = 0b10101100;  /* 172 */

    /* AND (論理積) */
    unsigned char and_result = a & b;
    /* 11001010
     & 10101100
     = 10001000 = 136 */

    /* OR (論理和) */
    unsigned char or_result = a | b;
    /* 11001010
     | 10101100
     = 11101110 = 238 */

    /* XOR (排他的論理和) */
    unsigned char xor_result = a ^ b;
    /* 11001010
     ^ 10101100
     = 01100110 = 102 */

    /* NOT (否定) */
    unsigned char not_result = ~a;
    /* ~11001010
     =  00110101 = 53 */
}

4.2.3 シフト演算の算術的意味

シフト演算は2の累乗による乗除算に対応します:

/*
 * シフト演算と算術演算の関係
 */

/* 左シフト = 2倍 */
x << 1  ≡  x × 2
x << n  ≡  x × 2ⁿ

unsigned char a = 5;       /* 00000101 = 5 */
a = a << 1;                /* 00001010 = 10 */
a = a << 2;                /* 00101000 = 40 */

/* 右シフト = 2で割る(切り捨て) */
x >> 1  ≡  x ÷ 2
x >> n  ≡  x ÷ 2ⁿ

unsigned char b = 40;      /* 00101000 = 40 */
b = b >> 1;                /* 00010100 = 20 */
b = b >> 2;                /* 00000101 = 5 */

/*
 * 注意: 符号付き整数の右シフトは実装依存
 *
 * 算術シフト: 符号ビットを維持
 * 論理シフト: 0で埋める
 */

4.3 ビットマスクの数学

4.3.1 マスクの生成

ビットマスクは、特定のビット位置を選択するための「型紙」です:

/*
 * ビットマスクの生成パターン
 */

/* 単一ビットのマスク */
unsigned char mask_bit_n = 1 << n;
/*
 * n=0: 00000001
 * n=1: 00000010
 * n=5: 00100000
 * n=7: 10000000
 */

/* n個の連続ビットのマスク */
unsigned char mask_n_bits = (1 << n) - 1;
/*
 * n=1: 00000001
 * n=4: 00001111
 * n=8: 11111111
 *
 * 数学的説明:
 *   2ⁿ - 1 = Σ(i=0 to n-1) 2ⁱ
 *   例: 2⁴ - 1 = 16 - 1 = 15 = 8 + 4 + 2 + 1 = 0b1111
 */

/* 位置 start から length ビットのマスク */
unsigned char mask_range = ((1 << length) - 1) << start;
/*
 * start=2, length=3: 00011100
 */

4.3.2 ビット操作の基本パターン

/*
 * ビット操作の4つの基本パターン
 *
 * これらは Minitalk のビット送受信の基礎となる
 */

/* 1. ビットの読み取り(GET) */
int get_bit(unsigned char byte, int pos)
{
    /*
     * 手順:
     *   1. byte を pos ビット右シフト
     *   2. 最下位ビットを 1 でマスク
     */
    return (byte >> pos) & 1;
}

/* 2. ビットを1にセット(SET) */
void set_bit(unsigned char *byte, int pos)
{
    /*
     * 手順:
     *   1. マスク (1 << pos) を生成
     *   2. OR 演算で対象ビットを1に
     *
     * 真理値表より: x | 1 = 1, x | 0 = x
     */
    *byte |= (1 << pos);
}

/* 3. ビットを0にクリア(CLEAR) */
void clear_bit(unsigned char *byte, int pos)
{
    /*
     * 手順:
     *   1. マスク (1 << pos) を生成
     *   2. マスクを反転 ~(1 << pos)
     *   3. AND 演算で対象ビットを0に
     *
     * 真理値表より: x & 0 = 0, x & 1 = x
     */
    *byte &= ~(1 << pos);
}

/* 4. ビットを反転(TOGGLE) */
void toggle_bit(unsigned char *byte, int pos)
{
    /*
     * 手順:
     *   1. マスク (1 << pos) を生成
     *   2. XOR 演算で対象ビットを反転
     *
     * 真理値表より: x ^ 1 = ~x, x ^ 0 = x
     */
    *byte ^= (1 << pos);
}

4.4 文字エンコーディングの歴史

4.4.1 電信符号の時代(1840年代)

文字のデジタルエンコーディングの歴史は、電信の発明に遡ります:

【1837年: Samuel Morse のモールス符号】

A: ・-
B: -・・・
C: -・-・
...

特徴:
  - 可変長符号
  - 頻度の高い文字(E, T)は短い
  - 情報理論の先駆け(後に Shannon が分析)


【1870年: Émile Baudot のボードー符号】

5ビットの固定長符号
2⁵ = 32文字を表現

00000 = null
00001 = E
00010 = LF
...

特徴:
  - 固定長 → 機械処理に適する
  - 大文字/数字の切り替えシフト
  - テレタイプの標準となる

4.4.2 ASCII の標準化(1963年)

ASCII(American Standard Code for Information Interchange)は、コンピュータ間の通信を標準化するために設計されました:

【ASCII 設計の原則(1963年)】

1. 7ビット(128文字)
   - 当時のテレタイプ互換
   - 8ビットマシンでパリティビット用に1ビット余裕

2. 制御文字(0-31, 127)
   - 通信制御(STX, ETX, EOT...)
   - 端末制御(BEL, BS, LF, CR...)

3. 印刷可能文字(32-126)
   - 記号、数字、アルファベット
   - 論理的な配置

4. 順序の合理性
   - 数字 '0'-'9' が連続(48-57)
   - 大文字 'A'-'Z' が連続(65-90)
   - 小文字 'a'-'z' が連続(97-122)
   - 大文字と小文字の差は32(ビット5)

ASCII コード表の構造:

【ASCIIの論理的構造】

上位3ビット:  000  001  010  011  100  101  110  111
             (0-) (1-) (2-) (3-) (4-) (5-) (6-) (7-)
             ────────────────────────────────────────
下位4ビット:
0000 (-0)    NUL  DLE  SP   0    @    P    `    p
0001 (-1)    SOH  DC1  !    1    A    Q    a    q
0010 (-2)    STX  DC2  "    2    B    R    b    r
0011 (-3)    ETX  DC3  #    3    C    S    c    s
0100 (-4)    EOT  DC4  $    4    D    T    d    t
0101 (-5)    ENQ  NAK  %    5    E    U    e    u
...
1111 (-F)    SI   US   /    ?    O    _    o    DEL

パターン:
  - 0x00-0x1F: 制御文字
  - 0x20-0x2F: 記号
  - 0x30-0x3F: 数字と記号
  - 0x40-0x5F: 大文字
  - 0x60-0x7F: 小文字

大文字→小文字: ビット5を立てる(+32)
  'A' (0x41) → 'a' (0x61)
  0b01000001 → 0b01100001
         ↑設定

4.4.3 Unicode への道(1991年)

ASCII は英語圏以外では不十分でした。様々な拡張(ISO-8859シリーズ、Shift_JIS等)が乱立し、「文字化け」問題が深刻化しました:

【文字コードの混乱】

1980年代:
  - ASCII (7ビット、128文字)
  - ISO-8859-1 (西欧、256文字)
  - ISO-8859-15 (€記号追加)
  - Shift_JIS (日本語)
  - EUC-JP (日本語)
  - GB2312 (中国語簡体字)
  - Big5 (中国語繁体字)
  - KS X 1001 (韓国語)
  ...

問題:
  1. 同じバイト値が異なる文字を表す
  2. 多言語テキストの混在が困難
  3. 変換時にデータ損失

解決: Unicode(1991年〜)
  - 世界中の文字を統一的に番号付け
  - 現在14万文字以上を定義

4.4.4 UTF-8 エンコーディング(1992年)

Ken Thompson と Rob Pike が設計した UTF-8 は、Unicode を効率的にエンコードする可変長方式です:

【UTF-8 の設計(1992年)】

設計者: Ken Thompson, Rob Pike(Plan 9 チーム)

要件:
  1. ASCII との後方互換性
  2. バイト境界での同期可能性
  3. ソート順序の保持

エンコーディング規則:

Code Point 範囲          バイト数   バイト形式
─────────────────────────────────────────────────
U+0000 - U+007F          1        0xxxxxxx
U+0080 - U+07FF          2        110xxxxx 10xxxxxx
U+0800 - U+FFFF          3        1110xxxx 10xxxxxx 10xxxxxx
U+10000 - U+10FFFF       4        11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

特徴:
  - ASCII文字は1バイト(そのまま)
  - 先頭バイトで文字長が分かる
  - 継続バイトは10xxxxxxの形式
  - バイト列のどこからでも文字境界を検出可能

UTF-8 の例:

【具体例】

'A' (U+0041):
  0x41 = 0b01000001
  → 1バイト: 0x41

'é' (U+00E9):
  0xE9 = 233 = 0b11101001
  → 2バイト: 0xC3 0xA9

  計算:
    110 00011  10 101001
        ↑↑      ↑↑↑↑↑↑
        0x03    0x29
    0x03 << 6 | 0x29 = 0xE9

'あ' (U+3042):
  0x3042 = 12354
  → 3バイト: 0xE3 0x81 0x82

  計算:
    1110 0011  10 000001  10 000010
         ↑↑↑↑    ↑↑↑↑↑↑    ↑↑↑↑↑↑
         0x3      0x01      0x02
    (0x3 << 12) | (0x01 << 6) | 0x02 = 0x3042

'😀' (U+1F600):
  → 4バイト: 0xF0 0x9F 0x98 0x80

4.5 Minitalk でのビットシリアライゼーション

4.5.1 MSB First(ネットワークバイトオーダー)

MSB(Most Significant Bit)First は、人間が読みやすく、ネットワークプロトコルで標準的な方式です:

/*
 * MSB First シリアライゼーション
 *
 * 最上位ビット(bit 7)から最下位ビット(bit 0)の順で送信
 * ネットワークバイトオーダーと同じ
 */

void send_char_msb_first(pid_t pid, unsigned char c)
{
    int bit_pos;

    /*
     * 例: 'A' = 65 = 0b01000001 の送信
     *
     * bit_pos=7: (c >> 7) & 1 = 0 → SIGUSR1
     * bit_pos=6: (c >> 6) & 1 = 1 → SIGUSR2
     * bit_pos=5: (c >> 5) & 1 = 0 → SIGUSR1
     * bit_pos=4: (c >> 4) & 1 = 0 → SIGUSR1
     * bit_pos=3: (c >> 3) & 1 = 0 → SIGUSR1
     * bit_pos=2: (c >> 2) & 1 = 0 → SIGUSR1
     * bit_pos=1: (c >> 1) & 1 = 0 → SIGUSR1
     * bit_pos=0: (c >> 0) & 1 = 1 → SIGUSR2
     *
     * 送信順: 0 1 0 0 0 0 0 1
     */
    bit_pos = 7;
    while (bit_pos >= 0)
    {
        if ((c >> bit_pos) & 1)
            kill(pid, SIGUSR2);
        else
            kill(pid, SIGUSR1);

        usleep(100);
        bit_pos--;
    }
}

/*
 * MSB First デシリアライゼーション
 *
 * 受信したビットを左シフトしながら蓄積
 */
static unsigned char g_char = 0;
static int g_bit_count = 0;

void receive_bit_msb_first(int signum)
{
    /*
     * 処理の流れ('A' を受信):
     *
     * 受信1(0): 0b00000000 << 1 = 0b00000000, | 0 → 0b00000000
     * 受信2(1): 0b00000000 << 1 = 0b00000000, | 1 → 0b00000001
     * 受信3(0): 0b00000001 << 1 = 0b00000010, | 0 → 0b00000010
     * 受信4(0): 0b00000010 << 1 = 0b00000100, | 0 → 0b00000100
     * 受信5(0): 0b00000100 << 1 = 0b00001000, | 0 → 0b00001000
     * 受信6(0): 0b00001000 << 1 = 0b00010000, | 0 → 0b00010000
     * 受信7(0): 0b00010000 << 1 = 0b00100000, | 0 → 0b00100000
     * 受信8(1): 0b00100000 << 1 = 0b01000000, | 1 → 0b01000001
     *
     * 結果: 0b01000001 = 65 = 'A'
     */

    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;
    }
}

4.5.2 LSB First(Intel バイトオーダー)

LSB(Least Significant Bit)First は、Intel プロセッサで使われるリトルエンディアンと親和性があります:

/*
 * LSB First シリアライゼーション
 *
 * 最下位ビット(bit 0)から最上位ビット(bit 7)の順で送信
 */

void send_char_lsb_first(pid_t pid, unsigned char c)
{
    int bit_pos;

    /*
     * 例: 'A' = 65 = 0b01000001 の送信
     *
     * bit_pos=0: (c >> 0) & 1 = 1 → SIGUSR2
     * bit_pos=1: (c >> 1) & 1 = 0 → SIGUSR1
     * bit_pos=2: (c >> 2) & 1 = 0 → SIGUSR1
     * bit_pos=3: (c >> 3) & 1 = 0 → SIGUSR1
     * bit_pos=4: (c >> 4) & 1 = 0 → SIGUSR1
     * bit_pos=5: (c >> 5) & 1 = 0 → SIGUSR1
     * bit_pos=6: (c >> 6) & 1 = 1 → SIGUSR2
     * bit_pos=7: (c >> 7) & 1 = 0 → SIGUSR1
     *
     * 送信順: 1 0 0 0 0 0 1 0
     */
    bit_pos = 0;
    while (bit_pos < 8)
    {
        if ((c >> bit_pos) & 1)
            kill(pid, SIGUSR2);
        else
            kill(pid, SIGUSR1);

        usleep(100);
        bit_pos++;
    }
}

/*
 * LSB First デシリアライゼーション
 *
 * 受信したビットを現在の位置にセット
 */
void receive_bit_lsb_first(int signum)
{
    /*
     * 処理の流れ('A' を受信):
     *
     * 受信1(1): g_char |= (1 << 0) → 0b00000001
     * 受信2(0): (変化なし)        → 0b00000001
     * 受信3(0): (変化なし)        → 0b00000001
     * 受信4(0): (変化なし)        → 0b00000001
     * 受信5(0): (変化なし)        → 0b00000001
     * 受信6(0): (変化なし)        → 0b00000001
     * 受信7(1): g_char |= (1 << 6) → 0b01000001
     * 受信8(0): (変化なし)        → 0b01000001
     *
     * 結果: 0b01000001 = 65 = 'A'
     */

    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;
    }
}

4.5.3 方式の選択と一貫性

【MSB First vs LSB First】

┌────────────────────┬────────────────────┐
│      MSB First     │      LSB First     │
├────────────────────┼────────────────────┤
│ 人間が読みやすい    │ 実装が若干シンプル  │
│ ネットワーク標準    │ x86と親和性あり    │
│ デバッグが容易      │                    │
├────────────────────┴────────────────────┤
│                                         │
│  重要: 送信側と受信側で必ず統一すること!  │
│                                         │
└─────────────────────────────────────────┘

Minitalk では通常 MSB First を推奨

4.6 UTF-8 対応(ボーナス)

4.6.1 UTF-8 バイト数の判定

/*
 * UTF-8 の先頭バイトから文字のバイト数を判定
 *
 * パターン:
 *   0xxxxxxx → 1バイト (ASCII)
 *   110xxxxx → 2バイト
 *   1110xxxx → 3バイト
 *   11110xxx → 4バイト
 */
int utf8_char_length(unsigned char first_byte)
{
    /* 最上位ビットが0 → ASCII(1バイト) */
    if ((first_byte & 0x80) == 0x00)
        return 1;

    /* 110xxxxx → 2バイト */
    if ((first_byte & 0xE0) == 0xC0)
        return 2;

    /* 1110xxxx → 3バイト */
    if ((first_byte & 0xF0) == 0xE0)
        return 3;

    /* 11110xxx → 4バイト */
    if ((first_byte & 0xF8) == 0xF0)
        return 4;

    /* 無効なバイト(継続バイトまたは不正) */
    return -1;
}

/*
 * マスクとの比較の数学的説明:
 *
 * 2バイト文字の判定:
 *   first_byte & 0xE0 == 0xC0
 *   0xE0 = 0b11100000 (上位3ビットをマスク)
 *   0xC0 = 0b11000000 (パターン 110xxxxx)
 *
 *   例: 0b11001010 & 0b11100000 = 0b11000000 ✓
 *       0b11101010 & 0b11100000 = 0b11100000 ✗
 */

4.6.2 UTF-8 文字列の送信

/*
 * UTF-8 文字列の送信
 *
 * 各バイトを順番に送信(UTF-8は自己同期式なので
 * バイト単位の送信で問題なし)
 */
int send_utf8_string(pid_t server_pid, const char *str)
{
    while (*str)
    {
        send_char_msb_first(server_pid, (unsigned char)*str);
        str++;
    }

    /* NUL終端を送信 */
    send_char_msb_first(server_pid, '\0');

    return 1;
}

/*
 * UTF-8 の自己同期性:
 *
 * バイト列のどこからでも文字境界を検出可能
 *   - 先頭バイト: 0xxxxxxx, 110xxxxx, 1110xxxx, 11110xxx
 *   - 継続バイト: 10xxxxxx
 *
 * もし途中でエラーが発生しても、
 * 次の先頭バイト(10xxxxxxでないバイト)から
 * 復帰可能
 */

4.6.3 受信側での UTF-8 処理

/*
 * UTF-8 文字の受信と検証
 */

typedef struct s_utf8_state
{
    unsigned char   buffer[4];      /* 最大4バイト */
    int             expected_bytes; /* 期待するバイト数 */
    int             received_bytes; /* 受信済みバイト数 */
}   t_utf8_state;

static t_utf8_state g_utf8 = {{0}, 0, 0};

void process_utf8_byte(unsigned char byte)
{
    if (g_utf8.expected_bytes == 0)
    {
        /* 新しい文字の開始 */
        g_utf8.expected_bytes = utf8_char_length(byte);

        if (g_utf8.expected_bytes < 0)
        {
            /* 無効なバイト */
            write(2, "[Invalid UTF-8]\n", 16);
            return;
        }

        g_utf8.buffer[0] = byte;
        g_utf8.received_bytes = 1;
    }
    else
    {
        /* 継続バイト */
        if ((byte & 0xC0) != 0x80)
        {
            /* 無効な継続バイト */
            write(2, "[Invalid continuation]\n", 23);
            g_utf8.expected_bytes = 0;
            g_utf8.received_bytes = 0;
            return;
        }

        g_utf8.buffer[g_utf8.received_bytes] = byte;
        g_utf8.received_bytes++;
    }

    /* 文字が完成したら出力 */
    if (g_utf8.received_bytes == g_utf8.expected_bytes)
    {
        write(1, g_utf8.buffer, g_utf8.expected_bytes);
        g_utf8.expected_bytes = 0;
        g_utf8.received_bytes = 0;
    }
}

4.7 エラー検出と訂正

4.7.1 パリティビット

最も単純なエラー検出方式:

/*
 * パリティビットの計算
 *
 * 偶数パリティ: 1の数が偶数になるようにパリティビットを設定
 * 奇数パリティ: 1の数が奇数になるようにパリティビットを設定
 */

int count_ones(unsigned char byte)
{
    int count = 0;
    int i;

    for (i = 0; i < 8; i++)
    {
        if (byte & (1 << i))
            count++;
    }

    return count;
}

int calculate_even_parity(unsigned char byte)
{
    return count_ones(byte) & 1;  /* 1の数が奇数なら1 */
}

/*
 * パリティ付き送信(9ビット/文字)
 */
void send_with_parity(pid_t pid, unsigned char c)
{
    int parity;

    /* 8ビットのデータを送信 */
    send_char_msb_first(pid, c);

    /* パリティビットを送信 */
    parity = calculate_even_parity(c);
    if (parity)
        kill(pid, SIGUSR2);
    else
        kill(pid, SIGUSR1);

    usleep(100);
}

/*
 * パリティの限界:
 *   - 1ビットエラーの検出のみ
 *   - 偶数個のエラーは検出不能
 *   - エラー訂正は不可能
 */

4.7.2 チェックサム

より堅牢なエラー検出:

/*
 * 簡易チェックサム(XOR)
 *
 * すべてのバイトのXOR
 */
unsigned char calculate_xor_checksum(const unsigned char *data, int len)
{
    unsigned char checksum = 0;
    int i;

    for (i = 0; i < len; i++)
        checksum ^= data[i];

    return checksum;
}

/*
 * 算術チェックサム(加算)
 *
 * すべてのバイトの合計の2の補数
 */
unsigned char calculate_sum_checksum(const unsigned char *data, int len)
{
    unsigned char sum = 0;
    int i;

    for (i = 0; i < len; i++)
        sum += data[i];

    return (~sum) + 1;  /* 2の補数 */
}

/*
 * 検証: データ + チェックサム の合計が 0 になるはず
 */
int verify_checksum(const unsigned char *data, int len, unsigned char checksum)
{
    unsigned char sum = 0;
    int i;

    for (i = 0; i < len; i++)
        sum += data[i];

    sum += checksum;

    return (sum == 0);
}

4.8 まとめ

この章では、ビット操作と文字エンコーディングの理論的基礎を学びました:

学んだこと

  • George Boole のブール代数(1854年)
- 論理の数学化 - Claude Shannon による電気回路への応用

  • ビット演算の代数
- AND, OR, XOR, NOT の真理値表 - シフト演算と算術

  • ビットマスクの数学
- マスク生成の原理 - GET, SET, CLEAR, TOGGLE パターン

  • 文字エンコーディングの歴史
- モールス符号からボードー符号へ - ASCII の標準化(1963年) - Unicode と UTF-8(1991-1992年)

  • Minitalk でのシリアライゼーション
- MSB First vs LSB First - UTF-8 対応

  • エラー検出
- パリティビット - チェックサム

次章の予告

第5章では、完全な Minitalk 実装 について学びます:

  • サーバーとクライアントの統合
  • エラー処理とリトライ
  • 最適化とデバッグ

---

参考文献:

  • Boole, G. (1854). An Investigation of the Laws of Thought. Walton and Maberly.
  • Shannon, C. E. (1937). "A Symbolic Analysis of Relay and Switching Circuits". Transactions of the AIEE, 57(12), 713-723.
  • American National Standards Institute. (1963). ASCII - American Standard Code for Information Interchange. ANSI X3.4.
  • The Unicode Consortium. (2021). The Unicode Standard, Version 14.0.
  • Pike, R., & Thompson, K. (1993). "Hello World or Καλημέρα κόσμε or こんにちは 世界". Proceedings of the USENIX Winter 1993 Conference.