ข้อสอบเก่า · Q11

Parity + Bit Stuffing + CRC

ข้อ 10 คะแนนที่ ทำถูกได้ 100% ทุกครั้ง เพราะไม่มีอะไรให้ตีความ — มีแค่ 3 กติกาที่ต้องเดินให้ครบ: นับเลข 1 · ยัด 0 หลัง 1 ห้าตัว · หาร XOR ทีละหลัก

ระดับง่าย (ถ้าซ้อมมา) ควรใช้ ~15 นาที 10 คะแนน อ่านคู่กับ บทที่ 12 (Parity/CRC) อ่านคู่กับ บทที่ 10 (Framing)

ทำไมข้อนี้ต้องได้เต็ม

ทั้งข้อไม่มีสูตรให้จำเลยสักตัว มีแต่ขั้นตอนกลไก และตรวจคำตอบเองได้ 100% ในห้องสอบ (parity → นับ 1 ซ้ำ · stuffing → ถอดกลับ · CRC → เอา T หารด้วย G ต้องได้ 0) · ข้อ c คนเดียว 6 คะแนน ซึ่งเป็นการหารยาว 8 บรรทัด ถ้าไม่ซ้อมมือมาจะช้าและพลาด — ให้ซ้อมด้วยเครื่องคำนวณโต้ตอบในหน้านี้จนหารได้เองโดยไม่ต้องคิด

โจทย์จริงจากข้อสอบปีที่แล้ว

Q11 (10 คะแนน · 15 นาที) — แสดงข้อมูลที่ส่งในช่องสัญญาณ

a. ใช้ odd parity บิต หากข้อมูลที่ต้องส่งเป็น 101111101 + รหัสหลังขีดของนักศึกษา (3 บิต) (2 คะแนน)
b. หากการสื่อสารที่เกิดขึ้นมีการใส่ flag = 01111110 (header และ Trailer) พร้อมทั้งทำ bit stuffing ข้อมูลที่ส่งจะเป็นอะไร (2 คะแนน)
c. หากใช้ CRC ที่มีค่า generator polynomial เป็น x³ + 1 ในการส่งข้อมูล 10110011 แสดงข้อมูลที่ถูกส่งในช่องสัญญาณ (6 คะแนน)

โจทย์ข้อ a เขียนกำกวม — ต้องทำทั้งสองแบบ

รหัสนักศึกษาของเจ้าของเว็บคือ 673040128-3 · คำว่า "รหัสหลังขีดของนักศึกษา (3 บิต)" ตีความได้ 2 ทาง และทั้งสองทางให้คำตอบคนละชุด:

การตีความ	ที่มา	3 บิตที่ได้
แบบ ① — เลขหลังขีดคือ 3 เขียนเป็นเลขฐานสอง 3 บิต	3₁₀ = 011₂	`011`
แบบ ② — เอา 3 บิตสุดท้ายของเลขหน้าขีด (128)	128₁₀ = 1000 0000₂ → 3 บิตท้าย	`000`

วิธีเอาตัวรอด: ทำแบบ ① เป็นคำตอบหลัก (ตรงกับคำว่า "หลังขีด" ที่สุด) แล้วเขียนบรรทัดเดียวว่า "หากตีความว่าเป็น 3 บิตสุดท้ายของ 128 = 000 จะได้ codeword เป็น … " — เขียนกำกับแบบนี้อาจารย์ตัดคะแนนไม่ลงทั้งสองกรณี · สิ่งที่ต้องเขียนเสมอคือ "ผมตีความว่า …"

คิดยังไง (แนวคิดใน 30 วินาที)

ทั้งสามข้อย่อยคือ "เติมของเข้าไปในสายบิต" เหมือนกันหมด ต่างกันแค่เติมอะไรและเติมเพื่ออะไร:

a · Parity — เติม 1 บิตท้าย

เพื่อตรวจจับ error · นับเลข 1 ทั้งหมด แล้วเติมบิตให้ยอดรวมเป็นคี่ (odd) · 1 บิตเท่านั้น ไม่ว่าข้อมูลจะยาวแค่ไหน

b · Bit stuffing — แทรก 0 กลางสาย

เพื่อไม่ให้ข้อมูลไปเหมือน flag · เจอ 1 ติดกันครบ 5 ตัวเมื่อไร ยัด 0 ตามหลังทันที แล้วเริ่มนับใหม่ · จบแล้วใส่ flag หัว-ท้าย

c · CRC — เติม r บิตท้าย

เพื่อตรวจจับ error แบบแรง · เติม 0 ท้าย r ตัว → หาร modulo-2 ด้วย G → เอาเศษไปแทนที่ 0 ที่เติม

ลำดับที่ถูกต้องถ้าโจทย์ให้ทำต่อกันเป็นสายเดียว

ข้อมูล → (a) เติม parity → (c) เติม CRC → (b) bit stuffing → ใส่ flag หัว-ท้าย · เหตุผล: parity/CRC เป็น เนื้อข้อมูล ที่ปลายทางต้องเอาไปตรวจ ส่วน stuffing กับ flag เป็นเรื่องของ การหั่นเฟรม ซึ่งปลายทางต้องถอดออกก่อนเป็นอันดับแรก · ในข้อสอบจริงข้อ a, b, c เป็นอิสระกัน (ข้อ c ใช้ข้อมูลชุดใหม่ 10110011 คนละชุดกับข้อ a) — อย่าเอาผลข้อ a ไปหาร CRC ในข้อ c เด็ดขาด

สูตร/ขั้นตอนที่ต้องใช้

Odd parity: (จำนวน 1 ในข้อมูล + parity bit) ต้องเป็นเลขคี่ ข้อมูลมี 1 เป็นจำนวนคี่ → parity = 0 · ข้อมูลมี 1 เป็นจำนวนคู่ → parity = 1

Bit stuffing: เจอ 1 ติดกันครบ 5 ตัว → แทรก 0 ทันที แล้วรีเซ็ตตัวนับ flag = 01111110 (1 หกตัวขนาบด้วย 0) ที่หัวและท้าย · ไม่ stuff ในตัว flag

CRC: T(x) = x^r·M(x) ⊕ R(x) สมการ 12.3 ของบทที่ 12 · r = ดีกรีของ G(x) · R(x) = เศษจากการหาร modulo-2

ตัวแปร	ความหมาย	ค่าในข้อสอบข้อ c
`M(x)`	ข้อมูลที่ต้องการส่ง (k บิต)	`10110011` → k = 8
`G(x)`	generator polynomial → แปลงเป็นสตริงบิตยาว r+1	x³+1 → `1001` (4 บิต)
`r`	ดีกรีของ G(x) = จำนวน `0` ที่เติมท้าย = จำนวนบิตของเศษ	3
`R(x)`	เศษจากการหาร modulo-2 (FCS) — ต้องยาว r บิตเสมอ	`111`
`T(x)`	code word ที่ส่งจริง = M ต่อด้วย R · ยาว n = k + r	`10110011111` → n = 11

แปลงโพลิโนเมียล → สตริงบิต ให้ถูก (ที่นี่คือจุดตายของข้อ c)

x³ + 1 มีเทอม x³ และ x⁰ · ตำแหน่งที่ต้องเขียนคือ x³ x² x¹ x⁰ = 4 ช่อง → ใส่ 1 ที่ x³ และ x⁰ ได้ 1001 · แต่ เติม 0 ท้ายข้อมูลแค่ 3 ตัว ไม่ใช่ 4
จำ: ตัวหารยาว r + 1 บิต · เติม 0 ท้ายข้อมูล r ตัว · เศษยาว r บิต — สามคำนี้เลขไม่เท่ากัน

ข้อ a — Odd Parity 2 คะแนน

แบบ ① — เลขหลังขีดคือ 3 → `011` คำตอบหลัก

ต่อข้อมูล — 101111101 + 011 = 101111101011 (12 บิต)
นับเลข 1 ทั้งหมด — ในส่วน 101111101 มี 7 ตัว · ในส่วน 011 มี 2 ตัว → รวม 9 ตัว
เช็คเงื่อนไข odd — 9 เป็นเลขคี่อยู่แล้ว ถ้าเติม 1 จะกลายเป็น 10 (คู่) ผิดเงื่อนไข → ต้องเติม parity = 0
ตรวจซ้ำ — codeword มี 1 อยู่ 9 ตัว = คี่ ✓

codeword = 1011 1110 1011 + 0 = 1011111010110 13 บิต (ข้อมูล 9 + รหัส 3 + parity 1) · parity bit = 0

แบบ ② — 3 บิตสุดท้ายของ 128 → `000`

ต่อข้อมูล — 101111101 + 000 = 101111101000 (12 บิต)
นับเลข 1 — 7 ตัว (รหัส 000 ไม่เพิ่มเลย)
7 เป็นคี่อยู่แล้ว → parity = 0 เหมือนกัน

codeword = 101111101000 + 0 = 1011111010000 13 บิตเท่ากัน · parity bit = 0 เท่ากัน แต่ ตัว codeword ต่างกัน

⚠ เฉลยที่ได้มานับจำนวนบิต 1 ผิด — ให้ยึดวิธีนับใหม่

เฉลยที่แจกมาใช้รหัสตัวอย่าง 663040112-7 (เลขหลังขีด 7 → 111) ⇒ ข้อมูลรวม = 101111101 + 111 = 101111101111 · เฉลยเขียนว่านับ 1 ได้ 11 ตัว แล้วสรุปว่าเป็นเลขคี่ จึงเติม parity = 0

ตรวจแล้วนับจริงได้ 10 ตัว (1·0·1111 1·0·1111 → 1 + 5 + 4 = 10) ซึ่งเป็นเลขคู่ ⇒ odd parity ต้องเติม 1 ไม่ใช่ 0 · codeword ที่ถูกของกรณีตัวอย่างนั้นคือ 1011111011111

วิธีคิดของเฉลยถูก แต่การนับผิด — ให้ยึดวิธีนี้เสมอ: "นับจำนวน 1 ทั้งหมด → odd parity ต้องทำให้จำนวน 1 รวมทั้ง codeword เป็นเลขคี่" ⇒ นับได้คี่อยู่แล้วเติม 0 · นับได้คู่เติม 1 · สำหรับรหัสของเราเอง (673040128-3 → 011) นับได้ 9 ตัวซึ่งเป็นคี่ จึงเติม 0 ⇒ 1011111010110 ถูกต้อง · ในห้องสอบให้เขียนบรรทัด "นับ 1 ได้ N ตัว" แล้ววงกลม N ไว้ — ถ้านับพลาดบรรทัดเดียว คำตอบทั้งข้อเปลี่ยน

ข่าวดีของข้อนี้

ทั้งสองการตีความให้ parity bit = 0 เหมือนกัน (เพราะ 011 มี 1 อยู่ 2 ตัวซึ่งเป็นเลขคู่ จึงไม่เปลี่ยนความคี่/คู่ของยอดรวม) ต่างกันแค่ตัว codeword · ดังนั้นถ้าเขียนขั้นตอน "นับได้ 7 (หรือ 9) ตัวซึ่งเป็นคี่ → parity = 0" ไว้ให้ชัด ก็ได้คะแนนกระบวนการเต็มไม่ว่าอาจารย์คิดแบบไหน

ข้อ b — Bit Stuffing + Flag 2 คะแนน

ข้อนี้ต่อยอดจากข้อ a — เอา codeword ที่ได้จากข้อ a (13 บิต) มาทำ bit stuffing แล้วประกบด้วย flag 01111110 ทั้งหัวและท้าย

แบบ ① — ไล่ทีละบิตจาก 1011111010110

  1        นับ 1 = 1
  0        เจอ 0 → รีเซ็ตตัวนับ
  1 1 1 1 1  นับครบ 5 ตัว !
  0        <- แทรก 0 ตรงนี้ แล้วเริ่มนับใหม่
  0 1 0 1 1 0  ที่เหลือไม่มี 1 ครบ 5 อีก

  ก่อน stuffing : 1011111010110      (13 บิต)
  หลัง stuffing : 10111110010110     (14 บิต — แทรกไป 1 ตัว)

01111110 10111110010110 01111110 เฟรมที่ส่งจริงบนสาย = 8 + 14 + 8 = 30 บิต · ขีดเส้นใต้ = 0 ที่ถูกยัดเข้าไป

แบบ ② (รหัส 000) — ต้นฉบับ 1011111010000 → หลัง stuffing = 10111110010000 (14 บิต แทรก 1 ตัวที่ตำแหน่งเดียวกัน) → เฟรม = 01111110 + 10111110010000 + 01111110 รวม 30 บิต เท่ากัน

ลองพิมพ์เองในเครื่องด้านล่าง

พิมพ์สตริงบิตอะไรก็ได้แล้วดูว่า 0 ถูกแทรกตรงไหน · เครื่องนี้ถอดกลับ (de-stuffing) ให้ดูด้วย เพื่อพิสูจน์ว่าปลายทางได้ข้อมูลเดิมกลับมาครบทุกบิต — ในห้องสอบวิธีตรวจข้อ b คือถอดกลับด้วยมือ ถ้าถอดแล้วไม่ตรงต้นฉบับ แปลว่า stuff ผิด

ข้อ c — CRC ด้วย G(x) = x³ + 1 6 คะแนน

แปลง G(x) เป็นสตริงบิต — x³ + 1 มีเทอม x³ กับ x⁰ · เขียนช่อง x³ x² x¹ x⁰ → 1001 (4 บิต) ⇒ r = 3
คูณข้อมูลด้วย x^r = เติม 0 ท้ายข้อมูล 3 ตัว
10110011 → 10110011000 (11 บิต)
หาร modulo-2 ด้วย 1001 — กฎ 3 ข้อ: ① ลบ = XOR ② ไม่มีทด ไม่มียืม ③ บิตซ้ายสุดของหน้าต่างเป็น 1 → ผลหาร 1 แล้ว XOR ด้วย G · เป็น 0 → ผลหาร 0 แล้วเลื่อนหน้าต่าง 1 ช่อง
ได้เศษ R = 111 (ยาว 3 บิตพอดี ✓)
เอาเศษไปแทนที่ 0 ที่เติมไว้ → T = 10110011 + 111

การหาร modulo-2 เต็มรูปแบบ — ลอกลงกระดาษได้เลย

  10110011000   <- M ต่อ 0 จำนวน r = 3 ตัว
  1001          <- XOR  (q=1)
  ----
  00100011000
   0000         <- XOR  (q=0)  บิตซ้ายเป็น 0 เลื่อนเฉย ๆ
   ----
   0100011000
    1001        <- XOR  (q=1)
    ----
    000111000
     0000       <- XOR  (q=0)
     ----
     00111000
      0000      <- XOR  (q=0)
      ----
      0111000
       1001     <- XOR  (q=1)
       ----
       011100
        1001    <- XOR  (q=1)
        ----
        01110
         1001   <- XOR  (q=1)
         ----
         0111   <- R = FCS = 111  (3 บิต)

  ผลหาร Q = 10100111   (ไม่ต้องเขียนก็ได้ ข้อสอบไม่ได้ถาม)
  T = 10110011 111 = 10110011111   (11 บิต)

ข้อมูลที่ถูกส่งในช่องสัญญาณ = 10110011111 n = k + r = 8 + 3 = 11 บิต · FCS = 111 · ไม่ใช่ 10110011000111 (นั่นคือเอา 0 ที่เติมไว้มาต่อด้วย ซึ่งผิด)

ตรวจคำตอบข้อ c ในห้องสอบ (ใช้เวลา 30 วินาที คุ้มมาก)

เอา T = 10110011111 หารด้วย 1001 อีกรอบ — ถ้าเศษเป็น 000 แปลว่าคำนวณถูก ถ้าไม่ใช่ศูนย์ แปลว่าหารพลาดตรงไหนสักที่ · นี่คือหลักการเดียวกับที่ฝั่งรับใช้ตรวจ error ทุกเฟรม (บทที่ 12) · เขียนการตรวจนี้ลงกระดาษด้วย อาจารย์เห็นแล้วให้คะแนนความเข้าใจ

เครื่องคำนวณ CRC แบบโต้ตอบ — พิมพ์เอง เดินการหารทีละบรรทัด

พิมพ์ข้อมูลกับ generator เองได้ · กด บรรทัดถัดไป เพื่อเดินการหารทีละขั้น จะเห็นว่าแต่ละบรรทัด XOR อะไรกับอะไร · ปุ่มสำเร็จรูปมีทั้งโจทย์ข้อสอบ ตัวอย่างในหนังสือ และเคสที่เกิด error

กับดักที่ทำให้เสียคะแนน

กับดักที่ 1 — เติม 0 ผิดจำนวน (เจอบ่อยที่สุดในข้อ c)

คำตอบผิดที่เจอจริง: "10110011 + 0000 = 101100110000" — เติม 4 ตัวเพราะเห็นตัวหาร 1001 ยาว 4 บิต · ผิด จำนวน 0 ที่เติม = ดีกรีของ G(x) = r = 3 ไม่ใช่ความยาวตัวหาร · ผลคือเศษจะออกมา 4 บิตแล้ว codeword ยาว 12 บิตซึ่งผิดทั้งข้อ · วิธีกันพลาด: เขียน "G(x) = x³+1 → r = 3 → เติม 0 สามตัว" เป็นบรรทัดแรกเสมอ

กับดักที่ 2 — ตอบผิดว่าอะไรคือ "ข้อมูลที่ถูกส่ง"

มีคำตอบผิด 3 แบบที่เจอประจำ:

คำตอบ	ถูก/ผิด	ทำไม
`111`	ผิด	นั่นคือเศษ ไม่ใช่ข้อมูลที่ส่ง โจทย์ถามหา T ทั้งก้อน
`10110011000111`	ผิด	เอา `0` ที่เติมชั่วคราวมาต่อด้วย — `0` พวกนั้นถูกแทนที่ด้วยเศษ ไม่ใช่ต่อท้าย
`10110011`	ผิด	ลืมเติม FCS เลย
`10110011111`	ถูก	M (8 บิต) ต่อด้วย R (3 บิต) = 11 บิต

เช็คด้วยความยาว: คำตอบต้องยาว n = k + r = 8 + 3 = 11 บิตเป๊ะ ถ้านับได้ 14 หรือ 8 แสดงว่าผิดแน่นอน

กับดักที่ 3 — หารแบบมีตัวยืม / เลื่อนหน้าต่างข้ามหลาย ๆ ช่อง

การหาร modulo-2 ไม่มีทดและไม่มียืม — 0 ⊕ 1 = 1 เฉย ๆ ไม่ใช่ "ยืมจากหลักหน้า" · และเมื่อบิตซ้ายสุดของหน้าต่างเป็น 0 ต้อง บันทึกผลหาร = 0 แล้วเลื่อนหน้าต่างไป 1 ช่อง ห้ามกระโดดข้ามไปหาบิต 1 ตัวถัดไปทีเดียว เพราะจำนวนบรรทัดจะไม่ครบและเศษจะเพี้ยน · จำนวนบรรทัดของการหารต้องเท่ากับ k = 8 บรรทัดพอดี (ตรงกับความยาวข้อมูล)

กับดักที่ 4 — เศษสั้นกว่า r บิต แล้วไม่เติม 0 นำหน้า

ถ้าหารแล้วได้เศษเป็น 11 ต้องเขียนเป็น 011 · ถ้าได้ 1 ต้องเขียน 001 — เศษต้องยาว r บิตเสมอ เพราะมันต้องไปนั่งในช่องที่เราเติม 0 ไว้พอดี ๆ · โจทย์ข้อนี้ได้ 111 ครบ 3 บิตอยู่แล้วจึงไม่เจอปัญหา แต่โจทย์ฝึกข้อ 5 เจอ (ได้ 001)

กับดักที่ 5 — bit stuffing แล้วลืมรีเซ็ตตัวนับ / stuff ทับ flag

① หลังยัด 0 เข้าไปแล้ว ต้องเริ่มนับ 1 ใหม่จากศูนย์ ไม่ใช่นับต่อ — สตริงอย่าง 11111111111 (1 สิบเอ็ดตัว) ต้องแทรก 2 ครั้ง ไม่ใช่ 1 ครั้ง
② ห้าม stuff ในตัว flag — flag 01111110 มี 1 หกตัวติดกัน ถ้าเผลอไปยัด 0 ในนั้น flag จะพังและปลายทางหาขอบเฟรมไม่เจอ
③ ถ้าโจทย์ถามว่า "เฟรมที่ส่ง" ต้องมี flag หัว-ท้ายเสมอ · ถ้าถาม "ข้อมูลหลัง stuffing" ให้ตอบเฉพาะส่วนกลาง — อ่านให้ดีว่าเขาถามอันไหน (ข้อสอบข้อนี้เขียนว่า "ใส่ flag (header และ Trailer) พร้อมทั้งทำ bit stuffing ข้อมูลที่ส่งจะเป็นอะไร" → ต้องมี flag)

เขียนยังไงให้ได้คะแนนเต็ม

ข้อ a (2 คะแนน)

เขียนบรรทัด "ผมตีความว่ารหัส 3 บิต = …"
เขียนข้อมูลที่ต่อแล้วเต็ม ๆ
เขียน "จำนวน 1 = 9 ตัว (คี่)"
เขียนกฎ "odd → รวมต้องเป็นคี่ → parity = 0"
ตีกรอบ codeword พร้อมบอกความยาว (13 บิต)

ข้อ b (2 คะแนน)

เขียนกฎ "เจอ 1 ครบ 5 → แทรก 0 แล้วนับใหม่"
ขีดเส้นใต้/วงกลม 0 ที่แทรก ให้อาจารย์เห็นชัด
เขียน flag หัว + ข้อมูล + flag ท้าย แยกช่องให้ชัด
บอกความยาว 8 + 14 + 8 = 30 บิต

ข้อ c (6 คะแนน)

บรรทัด "G(x) = x³+1 → 1001, r = 3"
บรรทัด "M·x³ = 10110011000"
การหารยาวเต็ม 8 บรรทัด — นี่คือส่วนที่ให้คะแนนมากที่สุด อย่าย่อ
บรรทัด "R = 111"
ตีกรอบ "T = 10110011111"
บรรทัดตรวจ: "T ÷ G = เศษ 000 ✓"

สิ่งที่ทำให้เสียคะแนนฟรี

เขียนแต่คำตอบสุดท้ายไม่มีการหาร → ข้อ c เหลือ 1–2 จาก 6
ไม่บอกว่าตีความรหัสนักศึกษายังไง → อาจารย์อาจนับว่าผิด
ไม่เขียน flag ในข้อ b
ไม่บอกความยาวบิต — เป็นตัวช่วยให้อาจารย์เห็นว่าเราเข้าใจโครงสร้าง

โจทย์ฝึก 5 ข้อ

ไล่จากง่ายไปยากกว่าของจริงเล็กน้อย · ทุกข้อตรวจเองได้ด้วยเครื่องคำนวณโต้ตอบด้านบน

ข้อ 1 ง่าย — ข้อมูล 1101011
(ก) หา parity bit แบบ odd และเขียน codeword
(ข) หา parity bit แบบ even และเขียน codeword
(ค) ถ้าฝั่งรับได้รับ 11010111 โดยตกลงกันว่าใช้ odd parity จะสรุปว่าอย่างไร

เฉลยข้อ 1

(ก) odd parity — นับ 1 ใน 1101011: ตำแหน่ง 1,2,4,6,7 → 5 ตัว (คี่)

เงื่อนไข odd = ยอดรวมต้องเป็นคี่ · ตอนนี้ 5 เป็นคี่อยู่แล้ว → เติม 0

codeword = 1101011 + 0 = 11010110ตรวจ: มี 1 อยู่ 5 ตัว = คี่ ✓

(ข) even parity — เงื่อนไข even = ยอดรวมต้องเป็นคู่ · 5 เป็นคี่ → ต้องเติม 1 ให้เป็น 6

codeword = 1101011 + 1 = 11010111ตรวจ: มี 1 อยู่ 6 ตัว = คู่ ✓

(ค) ฝั่งรับได้ 11010111 → นับ 1 ได้ 6 ตัว = คู่ แต่ตกลงกันว่าใช้ odd (ต้องเป็นคี่) → สรุปว่าเกิดความผิดพลาดในการส่ง · สังเกตว่าคำตอบข้อ (ข) กับข้อมูลที่รับในข้อ (ค) เป็นสตริงเดียวกัน — นี่คือเหตุผลว่าทำไม สองฝั่งต้องตกลงกันก่อนว่าใช้ even หรือ odd ไม่งั้นเฟรมที่ดีจะถูกมองว่าเสีย

ข้อ 2 ง่าย–กลาง — ข้อมูลที่จะส่งคือ 111110111110 (12 บิต) ใช้ flag 01111110 หัวและท้าย
(ก) หลัง bit stuffing ส่วนข้อมูลยาวกี่บิตและเป็นอะไร
(ข) เฟรมทั้งเฟรมบนสายยาวกี่บิต
(ค) ฝั่งรับถอด (de-stuffing) ยังไงให้ได้ข้อมูลเดิม

เฉลยข้อ 2

(ก) ไล่ทีละบิต (ตัวหนา = 0 ที่ถูกแทรก)

บิตที่	ค่า	ตัวนับ 1 ติดกัน	ทำอะไร
1–5	`11111`	1→2→3→4→5	ครบ 5 → แทรก `0` แล้วรีเซ็ตเป็น 0
6	`0`	0	ปกติ
7–11	`11111`	1→2→3→4→5	ครบ 5 → แทรก `0` อีกครั้ง
12	`0`	0	ปกติ

1111100 1111100 = 1111100111110012 บิต → 14 บิต (แทรกไป 2 ตัว)

(ข) เฟรมทั้งเฟรม = flag 8 + ข้อมูล 14 + flag 8 = 30 บิต

01111110 11111001111100 01111110

(ค) การถอดของฝั่งรับ — หา flag หัวและท้ายก่อนเพื่อรู้ขอบเฟรม จากนั้นไล่บิตในส่วนกลาง: เมื่อใดที่นับ 1 ติดกันได้ 5 ตัวแล้วบิตถัดไปเป็น 0 ให้ทิ้ง 0 ตัวนั้นทิ้งไป แล้วรีเซ็ตตัวนับ · ทำแบบนี้จะได้ 111110111110 กลับมาครบ 12 บิตพอดี · ข้อควรระวัง: ถ้านับได้ 5 ตัวแล้วบิตถัดไปเป็น 1 (คือมี 1 หกตัว) นั่นคือ flag ไม่ใช่ข้อมูล → แปลว่าเจอขอบเฟรม

ข้อ 3 กลาง — ส่งข้อมูล 1101011011 (10 บิต) ด้วย CRC ที่มี generator polynomial G(x) = x⁴ + x + 1
(ก) เขียน G(x) เป็นสตริงบิต และบอกว่า r เท่ากับเท่าใด
(ข) แสดงการหาร modulo-2 และหาค่า FCS
(ค) เขียนข้อมูลที่ถูกส่งจริง พร้อมบอกความยาว

เฉลยข้อ 3

(ก) x⁴ + x + 1 มีเทอม x⁴, x¹, x⁰ · เขียนช่อง x⁴ x³ x² x¹ x⁰ → 10011 (5 บิต) ⇒ r = 4 (ดีกรีสูงสุด) → เติม 0 ท้ายข้อมูล 4 ตัว

(ข) การหาร — 1101011011 + 0000 = 11010110110000 (14 บิต) หารด้วย 10011

  11010110110000
  10011          XOR (q=1)
  -----
  01001110110000
   10011         XOR (q=1)
   -----
   0000010110000
    00000        XOR (q=0)
    -----
    000010110000
     00000       XOR (q=0)
     -----
     00010110000
      00000      XOR (q=0)
      -----
      0010110000
       00000     XOR (q=0)
       -----
       010110000
        10011    XOR (q=1)
        -----
        00101000
         00000   XOR (q=0)
         -----
         0101000
          10011  XOR (q=1)
          -----
          001110
           00000 XOR (q=0)
           -----
           01110  R = FCS = 1110

สังเกต: มี 10 บรรทัดพอดี = ความยาวข้อมูล 10 บิต ✓ และ 6 บรรทัดในนั้นเป็น q=0 (เลื่อนหน้าต่างเฉย ๆ) ซึ่งห้ามข้าม

(ค)

T = 1101011011 + 1110 = 11010110111110 n = k + r = 10 + 4 = 14 บิต · ตรวจ: T ÷ 10011 ได้เศษ 0000 ✓

บทเรียน: โจทย์นี้ FCS ยาว 4 บิตเพราะ r = 4 — ความยาวเศษ = r เสมอ ไม่เกี่ยวกับความยาวข้อมูล · ข้อมูลจะยาว 10 หรือ 1000 บิต FCS ก็ยัง 4 บิตเท่าเดิม นี่คือข้อดีของ CRC (overhead คงที่)

ข้อ 4 กลาง — ใช้ค่าจากข้อสอบจริง: ต้นทางส่ง T = 10110011111 ด้วย G = 1001
(ก) ถ้าฝั่งรับได้รับครบถ้วน จงแสดงว่าเศษเป็นศูนย์
(ข) ถ้าระหว่างทาง บิตที่ 5 (นับจากซ้าย) พลิกจาก 0 เป็น 1 ฝั่งรับได้ 10111011111 จงแสดงว่าตรวจจับได้
(ค) CRC ที่ใช้ G ยาว 4 บิต ตรวจจับ error แบบไหนได้บ้าง

เฉลยข้อ 4

(ก) กรณีไม่มี error — ฝั่งรับหาร T ทั้งก้อนด้วย G โดยไม่ต้องเติม 0 เพิ่ม (ต่างจากฝั่งส่ง!)

  10110011111
  1001         XOR (q=1)
  ----
  00100011111
   0000        XOR (q=0)
   ----
   0100011111
    1001       XOR (q=1)
    ----
    000111111
     0000      XOR (q=0)
     ----
     00111111
      0000     XOR (q=0)
      ----
      0111111
       1001    XOR (q=1)
       ----
       011011
        1001   XOR (q=1)
        ----
        01001
         1001  XOR (q=1)
         ----
         0000  R = 000  →  ไม่มีความผิดพลาด ✓

(ข) กรณีมี error 1 บิต — ฝั่งรับได้ 10111011111 หารด้วย 1001 ได้เศษ 001 ≠ 000

R = 001 ≠ 0 → ตรวจพบความผิดพลาด → ทิ้งเฟรมและขอส่งใหม่

ลองพิมพ์ 10111011111 กับ 1001 ลงในเครื่องคำนวณด้านบนเพื่อดูการหารเต็ม ๆ (ปุ่ม "เคส error" ใส่ให้แล้ว)

(ค) ความสามารถของ CRC เมื่อ G(X) มีจำนวนบิตเป็น R (ในที่นี้ R = 4) ตามบทที่ 12:

ตรวจจับ error 1 บิต ได้ทุกกรณี ✓ (เคสข้อ ข นี่แหละ)
ตรวจจับ error 2 บิต ได้ทุกกรณี ✓
ตรวจจับ error ที่เป็นจำนวนคี่ ได้ทุกกรณี ✓
ตรวจจับ burst error ที่สั้นกว่า R บิต (คือสั้นกว่า 4 บิต) ได้ทุกกรณี ✓
burst ที่ยาว ≥ R บิต — ตรวจจับได้ แต่ไม่ทุกกรณี △

ข้อ 5 ยากกว่าของจริง — ทำครบทั้งสายเหมือนโจทย์จริงแต่ต่อกันเป็นเส้นเดียว
ข้อมูลดิบ 100111110 (9 บิต)
(ก) เติม odd parity 1 บิต
(ข) นำผลจาก (ก) ไปทำ CRC ด้วย G(x) = x³ + x + 1
(ค) นำผลจาก (ข) ไปทำ bit stuffing แล้วประกบ flag 01111110
(ง) บอกความยาวเฟรมสุดท้าย และอธิบายว่าปลายทางต้องถอดย้อนกลับตามลำดับใด

เฉลยข้อ 5

(ก) Odd parity — 100111110 มี 1 อยู่ 6 ตัว (คู่) · odd ต้องการยอดคี่ → เติม 1

codeword = 100111110110 บิต · ตรวจ: มี 1 อยู่ 7 ตัว = คี่ ✓ (ข้อนี้ parity = 1 ต่างจากข้อสอบจริงที่ได้ 0)

(ข) CRC ด้วย G(x) = x³ + x + 1 · เทอม x³, x¹, x⁰ → ช่อง x³ x² x¹ x⁰ = 1011 (4 บิต) ⇒ r = 3 → เติม 000 ท้าย

  1001111101000
  1011           XOR (q=1)
  ----
  0010111101000
   0000          XOR (q=0)
   ----
   010111101000
    1011         XOR (q=1)
    ----
    00001101000
     0000        XOR (q=0)
     ----
     0001101000
      0000       XOR (q=0)
      ----
      001101000
       0000      XOR (q=0)
       ----
       01101000
        1011     XOR (q=1)
        ----
        0110000
         1011    XOR (q=1)
         ----
         011100
          1011   XOR (q=1)
          ----
          01010
           1011  XOR (q=1)
           ----
           0001  R = 001  ← ต้องเขียน 0 นำหน้าให้ครบ 3 บิต!

T = 1001111101 + 001 = 1001111101001n = 10 + 3 = 13 บิต · ตรวจ: T ÷ 1011 = เศษ 000 ✓

จุดที่คนพลาด: เศษออกมาเป็น 1 ตัวเดียว ต้องเขียนเป็น 001 ไม่ใช่ 1 — ถ้าเขียนแค่ 1 codeword จะยาว 11 บิตซึ่งผิด

(ค) Bit stuffing + flag — ไล่บิตของ 1001111101001

1 (นับ 1) · 0 (รีเซ็ต) · 0 · 11111 (ครบ 5 → แทรก 0 รีเซ็ต) · 0 · 1 · 001 → ไม่มีจุดอื่นที่ครบ 5 อีก

ก่อน stuffing : 1001111101001 (13 บิต)
หลัง stuffing : 10011111001001 (14 บิต — แทรก 1 ตัว)

เฟรมบนสาย : 01111110 10011111001001 01111110

(ง) ความยาวและลำดับการถอด

ความยาวเฟรม = 8 + 14 + 8 = 30 บิตข้อมูลดิบ 9 บิต → ส่งจริง 30 บิต = overhead 21 บิต (233%) เพราะเฟรมสั้นมาก

ปลายทางถอดย้อนลำดับตรงข้ามกับตอนใส่เสมอ:

หา flag หัว-ท้าย เพื่อรู้ขอบเฟรม แล้วตัดทิ้ง → เหลือ 14 บิต
de-stuffing — เจอ 1 ครบ 5 ตัวแล้วตามด้วย 0 ให้ทิ้ง 0 ตัวนั้น → เหลือ 1001111101001 (13 บิต)
ตรวจ CRC — หาร 13 บิตนี้ด้วย 1011 ต้องได้เศษ 000 → ถ้าไม่ใช่ ทิ้งเฟรม
ตัด FCS 3 บิตท้ายทิ้ง → เหลือ 1001111101 (10 บิต)
ตรวจ parity — นับ 1 ได้ 7 ตัว = คี่ ✓ ตรงกับ odd → ตัด parity bit ท้ายทิ้ง เหลือข้อมูลดิบ 100111110 (9 บิต) ✓

เช็คความเข้าใจ

ใช้ odd parity กับข้อมูล 10110010 — parity bit ต้องเป็นอะไร?

นับ 1 ใน 10110010 → ตำแหน่ง 1, 3, 4, 7 = 4 ตัว = คู่ · เงื่อนไข odd คือ (ข้อมูล + parity) ต้องเป็นคี่ ดังนั้นต้องเติม 1 ให้ได้ 5 ตัว · parity bit ไม่ได้ขึ้นกับบิตสุดท้ายของข้อมูล แต่ขึ้นกับจำนวนเลข 1 ทั้งหมด

G(x) = x⁵ + x² + 1 — ต้องเติม 0 ท้ายข้อมูลกี่ตัว และตัวหารยาวกี่บิต?

ดีกรีสูงสุดคือ 5 ⇒ r = 5 → เติม 0 ท้ายข้อมูล 5 ตัว และเศษยาว 5 บิต · ส่วนสตริงบิตของตัวหารต้องมี r + 1 = 6 ช่อง (x⁵ x⁴ x³ x² x¹ x⁰) → ใส่ 1 ที่ x⁵, x², x⁰ ได้ 100101 · ตัวเลือกสุดท้ายผิดเพราะ "จำนวนเทอม" (3 เทอม) ไม่เกี่ยวกับจำนวน 0 ที่เติม

ข้อมูล 011111111 ผ่าน bit stuffing แล้วส่วนข้อมูลจะเป็นอะไร?

ไล่ทีละบิต: 0(รีเซ็ต) → 1(1) 1(2) 1(3) 1(4) 1(5 → แทรก 0 ทันที รีเซ็ตตัวนับ) → 1(1) 1(2) 1(3) จบ · ได้ 0111110111 = 10 บิต · กติกาคือแทรกทุกครั้งที่ครบ 5 ไม่ใช่ครั้งเดียวต่อเฟรม และแทรกตามหลังไม่ใช่ข้างหน้า

เก็บก่อนออกจากข้อนี้

a: 101111101 + 011 มี 1 อยู่ 9 ตัว (คี่) → odd parity bit = 0 → codeword 1011111010110 · เขียนกำกับเสมอว่าตีความรหัส 3 บิตแบบไหน
b: เจอ 1 ครบ 5 → ยัด 0 แล้วนับใหม่ · ได้ 10111110010110 (14 บิต) → เฟรม 01111110+ข้อมูล+01111110 = 30 บิต
c: x³+1 → 1001, r = 3 เติม 0 สามตัว → เศษ 111 → T = 10110011111 (11 บิต)
ตรวจทุกครั้ง: T ÷ G ต้องได้เศษ 000 · ความยาว T ต้อง = k + r · จำนวนบรรทัดการหาร = k
เศษต้องยาว r บิตเสมอ — ได้ 11 ต้องเขียน 011