เลขฐานและลอจิกดิจิทัล

ทำไมต้องรู้

ทุกอย่างที่โดรนรับรู้และสั่งงาน ไม่ว่าจะเป็นค่าความเร่งจาก IMU พิกัด GNSS หรือคำสั่งให้บินกลับ ถูกเก็บและส่งเป็น บิต คือค่า 0 กับ 1 เท่านั้น ถ้าอ่านบิตเป็น เราจะถอดข้อความ telemetry ได้เอง เข้าใจว่าทำไมค่าความเร็วติดลบจึงกลายเป็นเลข 65286 เมื่ออ่านผิดชนิด และรู้ว่าเครื่องรับจับข้อมูลที่เสียระหว่างทางได้อย่างไร

โมดูลนี้ต่อจาก UAT 104 โมดูล 4 ที่อ่านไฟล์ .tlog ด้วย pymavlink คราวนี้เราจะลงไปดูถึงระดับบิตว่าไลบรารีทำอะไรให้เรา

เลขฐานสองและฐานสิบหก

เลขฐานสอง (binary) ใช้เพียงเลข 0 และ 1 แต่ละหลักเรียกว่า บิต (bit) ค่าประจำหลักเพิ่มทีละสองเท่า เหมือนเลขฐานสิบที่เพิ่มทีละสิบเท่า บิตแปดตัวรวมเป็น ไบต์ (byte) เก็บค่าได้ 0 ถึง 255

เลขฐานสิบหก (hexadecimal) ใช้ 0–9 และ A–F เลขฐานสิบหกหนึ่งหลักแทนบิตได้พอดีสี่ตัว หนึ่งไบต์จึงเขียนเป็นเลขฐานสิบหกสองหลัก โปรแกรมเมอร์นิยมใช้เพราะสั้นกว่าและอ่านง่ายกว่าฐานสองมาก ใน Python เขียนเลขฐานสองขึ้นต้นด้วย 0b และฐานสิบหกขึ้นต้นด้วย 0x

for n in [5, 13, 200, 255]:
    print(f"{n:>3}  bin {n:08b}  hex 0x{n:02X}")
print(int("11001000", 2), int("C8", 16), int("0xFD", 16))

  5  bin 00000101  hex 0x05
 13  bin 00001101  hex 0x0D
200  bin 11001000  hex 0xC8
255  bin 11111111  hex 0xFF
200 200 253

ไบต์แรกของเฟรม MAVLink 2 คือ 0xFD ซึ่งเท่ากับ 253 อย่างที่เห็นในบรรทัดสุดท้าย

จำนวนเต็มติดลบแบบ two’s complement

คอมพิวเตอร์เก็บจำนวนเต็มติดลบด้วยวิธี two’s complement คือค่า $-x$ ในพื้นที่ $n$ บิตเก็บเป็นเลข $2^n-x$ ข้อดีคือวงจรบวกลบตัวเดียวใช้ได้ทั้งเลขบวกและเลขลบ บิตซ้ายสุดเป็น 1 เมื่อเลขติดลบ จำนวนเต็ม 16 บิตแบบมีเครื่องหมายจึงเก็บได้ตั้งแต่ −32768 ถึง 32767

ใน MAVLink ข้อความ GLOBAL_POSITION_INT เก็บความเร็วแนวดิ่ง vz เป็นจำนวนเต็ม 16 บิตมีเครื่องหมาย หน่วย cm/s ถ้าโดรนไต่ขึ้นด้วย 2.5 m/s ค่า vz จะเป็น −250 เพราะแกน z ของกรอบ NED ชี้ลงดิน

import struct

raw = struct.pack("<h", -250)
print(raw.hex(" "), f"{int.from_bytes(raw, 'little'):016b}")
print(struct.unpack("<h", raw)[0], struct.unpack("<H", raw)[0])
print((1 << 16) - 250)

06 ff 1111111100000110
-250 65286
65286

รหัส <h บอกให้ struct อ่านเป็นจำนวนเต็ม 16 บิตมีเครื่องหมาย เรียงไบต์แบบ little-endian (ไบต์ค่าน้อยมาก่อน) ซึ่ง MAVLink ใช้ ถ้าอ่านไบต์เดียวกันผิดเป็น <H (ไม่มีเครื่องหมาย) จะได้ 65286 ซึ่งเท่ากับ $2^{16}-250$ พอดี ค่าความเร็วแปลก ๆ แบบนี้ในกราฟมักเกิดจากอ่านชนิดข้อมูลผิด

print(struct.pack(">f", 0.1).hex(), f"{struct.unpack('>f', struct.pack('>f', 0.1))[0]:.20f}")

3dcccccd 0.10000000149011611938

เกตตรรกะและตารางความจริง

เกตตรรกะ (logic gate) เป็นวงจรที่รับบิตเข้าแล้วให้บิตออกตามกฎหนึ่ง เกตพื้นฐานได้แก่ AND (ออก 1 เมื่อทุกขาเป็น 1), OR (ออก 1 เมื่อมีขาใดเป็น 1), NOT (กลับค่า) และ XOR (ออก 1 เมื่อสองขาต่างกัน) ตารางความจริง แสดงผลของทุกกรณีที่เป็นไปได้ สำหรับสองขาเข้ามี $2^2=4$ กรณี

from itertools import product

print("A B | AND OR XOR NAND")
for a, b in product([0, 1], repeat=2):
    print(a, b, "|", a & b, " ", a | b, " ", a ^ b, "  ", 1 - (a & b))

A B | AND OR XOR NAND
0 0 | 0   0   0    1
0 1 | 0   1   1    1
1 0 | 0   1   1    1
1 1 | 1   1   0    0

ในภาษา Python ตัวดำเนินการ & | ^ ทำงานกับบิตโดยตรง เราใช้ตัวดำเนินการเหล่านี้กับ บิตมาสก์ (bitmask) เพื่ออ่านสถานะหลายอย่างจากเลขตัวเดียว เช่น บิตที่ 7 ของ base_mode ใน HEARTBEAT บอกว่าโดรนติดอาวุธมอเตอร์ (armed) หรือยัง

MAV_MODE_FLAG_SAFETY_ARMED = 0b1000_0000
MAV_MODE_FLAG_CUSTOM_MODE_ENABLED = 0b0000_0001
base_mode = 0x51
print(f"{base_mode:08b}", bool(base_mode & MAV_MODE_FLAG_SAFETY_ARMED), bool(base_mode & MAV_MODE_FLAG_CUSTOM_MODE_ENABLED))
armed = base_mode | MAV_MODE_FLAG_SAFETY_ARMED
print(f"{armed:08b}", hex(armed))

01010001 False True
11010001 0xd1

จากเกตสู่วงจรบวก

เอาเกต XOR กับ AND มาต่อกันจะได้ วงจรบวกครึ่ง (half adder) ที่บวกเลขหนึ่งบิตสองตัว ได้ผลบวก $S=A\oplus B$ และตัวทด $C=A\cdot B$ ต่อวงจรบวกครึ่งสองตัวจะได้ วงจรบวกเต็ม (full adder) ที่รับตัวทดจากหลักก่อนหน้าได้ และต่อวงจรบวกเต็มหลายตัวเรียงกันจะบวกเลขหลายบิตได้ หน่วยคำนวณ (ALU) ใน CPU สร้างจากหลักการนี้

def half_adder(a, b):
    return a ^ b, a & b


def full_adder(a, b, cin):
    s1, c1 = half_adder(a, b)
    s, c2 = half_adder(s1, cin)
    return s, c1 | c2


def add_4bit(x, y):
    carry, bits = 0, []
    for i in range(4):
        s, carry = full_adder((x >> i) & 1, (y >> i) & 1, carry)
        bits.append(s)
    return sum(b << i for i, b in enumerate(bits)), carry


for x, y in [(5, 6), (9, 7), (15, 1)]:
    total, carry = add_4bit(x, y)
    print(f"{x} + {y} -> sum {total:04b} ({total}), carry {carry}")

5 + 6 -> sum 1011 (11), carry 0
9 + 7 -> sum 0000 (0), carry 1
15 + 1 -> sum 0000 (0), carry 1

$9+7=16$ ใหญ่เกินกว่าที่ 4 บิตเก็บได้ (สูงสุด 15) ผลบวกจึงวนกลับเป็น 0 และตัวทดเป็น 1 ปรากฏการณ์นี้เรียกว่า ล้น (overflow) ตัวนับลำดับ (sequence) ของ MAVLink ขนาด 8 บิตก็วนจาก 255 กลับเป็น 0 ด้วยเหตุผลเดียวกัน

ตรวจความผิดพลาดด้วย parity และ CRC

คลื่นวิทยุอาจทำให้บิตบางตัวพลิกระหว่างทาง เครื่องรับจึงต้องมีวิธีรู้ว่าข้อมูลเสีย วิธีง่ายที่สุดคือ บิตพาริตี (parity bit) ที่นับว่ามีเลข 1 เป็นจำนวนคู่หรือคี่ แต่จับได้เฉพาะเมื่อบิตพลิกเป็นจำนวนคี่ตัว

วิธีที่แข็งแรงกว่าคือ CRC (cyclic redundancy check) ที่ใช้ XOR และการเลื่อนบิตคำนวณรหัสตรวจสอบจากข้อมูลทั้งเฟรม MAVLink ใช้ CRC-16/MCRF4XX ขนาด 2 ไบต์ ปิดท้ายทุกเฟรม และเติมค่าพิเศษ CRC_EXTRA ของแต่ละชนิดข้อความเข้าไปในการคำนวณด้วย ถ้าผู้ส่งกับผู้รับเข้าใจรูปแบบข้อความไม่ตรงกัน CRC จะไม่ตรง ข้อความนั้นจึงถูกทิ้ง

def crc16_mcrf4xx(data, crc=0xFFFF):
    for byte in data:
        tmp = byte ^ (crc & 0xFF)
        tmp = (tmp ^ (tmp << 4)) & 0xFF
        crc = ((crc >> 8) ^ (tmp << 8) ^ (tmp << 3) ^ (tmp >> 4)) & 0xFFFF
    return crc


print(hex(crc16_mcrf4xx(b"123456789")))

0x6f91

ค่า 0x6F91 จากข้อความทดสอบ “123456789” ตรงกับค่าตรวจสอบมาตรฐานของ CRC-16/MCRF4XX แสดงว่าฟังก์ชันเขียนถูก ต่อไปลองกับเฟรม HEARTBEAT จริงที่สร้างด้วย pymavlink

frame = bytes.fromhex("fd 09 00 00 00 01 01 00 00 00 04 00 00 00 02 03 51 03 03 7e 22")
header, payload, crc_bytes = frame[:10], frame[10:19], frame[19:]
msg_id = int.from_bytes(header[7:10], "little")
custom_mode = int.from_bytes(payload[0:4], "little")
print(len(frame), msg_id, custom_mode, payload[4], payload[5], hex(payload[6]))

HEARTBEAT_CRC_EXTRA = 50
crc = crc16_mcrf4xx(frame[1:19] + bytes([HEARTBEAT_CRC_EXTRA]))
print(hex(crc), crc == int.from_bytes(crc_bytes, "little"))

damaged = bytearray(frame)
damaged[16] ^= 0b1000_0000
crc_bad = crc16_mcrf4xx(bytes(damaged[1:19]) + bytes([HEARTBEAT_CRC_EXTRA]))
print(hex(crc_bad), crc_bad == int.from_bytes(crc_bytes, "little"))

21 0 4 2 3 0x51
0x227e True
0xf10 False

ปฏิบัติการประจำโมดูล

ข้อผิดพลาดที่พบบ่อย

สรุป

• บิตแปดตัวเป็นหนึ่งไบต์ ฐานสิบหกหนึ่งหลักแทนสี่บิต จึงนิยมใช้เขียนไบต์
• จำนวนติดลบเก็บแบบ two’s complement ส่วนเลขทศนิยมเก็บตาม IEEE 754 ซึ่งแทนบางค่าได้ไม่ตรง
• เกต AND OR XOR NOT ต่อกันเป็นวงจรบวก และบิตมาสก์ใช้อ่านธงสถานะจากเลขตัวเดียว
• MAVLink ตรวจความผิดพลาดด้วย CRC-16/MCRF4XX ที่รวม CRC_EXTRA แต่ CRC ไม่ได้ป้องกันการปลอมข้อความ

แบบฝึกตรวจความเข้าใจ

1. 0b10110 มีค่าเท่าใดในฐานสิบ
2. 0x3F มีค่าเท่าใดในฐานสิบ และเขียนเป็นเลขฐานสองแปดบิตอย่างไร
3. จำนวนเต็ม 8 บิตมีเครื่องหมายค่า −1 เก็บเป็นไบต์ค่าใดในฐานสิบหก
4. ถ้า A = 1 และ B = 1 วงจรบวกครึ่งให้ผลบวกและตัวทดเท่าใด
5. ทำไม MAVLink จึงเติม CRC_EXTRA ลงในการคำนวณ CRC