AlgoVerse

کد همینگ (۷،۴)

به ۴ بیت داده ۳ بیت توازن اضافه می‌کند طوری که اگر یک بیت در راه خراب شود، «نشانگر» دقیقاً جای آن را بگوید و درستش کند.

در کد همینگ (۷،۴) موقعیت‌های ۱، ۲ و ۴ (توان‌های ۲) بیت توازن‌اند و بقیه داده:

ادامه‌ی توضیح ↓
ورودی:
data="1011" · error=5خروجی PDF

داده‌ی 1011؛ کلمه‌ی کد 0110011 است. بیت ۵ در راه خراب می‌شود و نشانگر دقیقاً ۵ را نشان می‌دهد.

  1. def hamming(data, error):
  2. # Positions 1 … 7 hold p1 p2 d1 p3 d2 d3 d4; c[k - 1] is the bit at position k.
  3. d = [int(b) for b in data]
  4. c = [0, 0, d[0], 0, d[1], d[2], d[3]]
  5. table = [["p1", "p2", "d1", "p3", "d2", "d3", "d4"], c]
  6. c[0] = c[2] ^ c[4] ^ c[6]
  7. c[1] = c[2] ^ c[5] ^ c[6]
  8. c[3] = c[4] ^ c[5] ^ c[6]
  9. sent = "".join(str(b) for b in c)
  10. if error:
  11. c[error - 1] = c[error - 1] ^ 1
  12. # Each check covers the positions whose number has that bit set; together they spell the bad position.
  13. s1 = c[0] ^ c[2] ^ c[4] ^ c[6]
  14. s2 = c[1] ^ c[2] ^ c[5] ^ c[6]
  15. s4 = c[3] ^ c[4] ^ c[5] ^ c[6]
  16. syndrome = s1 + 2 * s2 + 4 * s4
  17. if syndrome:
  18. c[syndrome - 1] = c[syndrome - 1] ^ 1
  19. decoded = f"{c[2]}{c[4]}{c[5]}{c[6]}"
  20. return decoded

ناوردا: هر موقعیت ۱ تا ۷ در مجموعه‌ی متفاوتی از بررسی‌ها هست (همان بیت‌های شماره‌اش)؛ پس الگوی بررسی‌های ناموفق جای خطا را یکتا مشخص می‌کند.

شروع اجرا

0123
1011
sent—
syndrome—
decoded—

جدول هنوز خالی است.

متغیرهای محلی

data'1011'
error5

نارنجی = در همین گام عوض شد

Call stack

  1. hamming()خط 1
گام ۱ از ۱۸
خط سیاه = encoded, syndrome · خط نارنجی = گام کلیدیparity: 0/3 · encoded: 0/1 · flip: 0/1 · syndrome: 0/1 · corrected: 0/1 · decoded: 0/1
    توضیح

    ایده

    در کد همینگ (۷،۴) موقعیت‌های ۱، ۲ و ۴ (توان‌های ۲) بیت توازن‌اند و بقیه داده:

    • p1 موقعیت‌هایی را بررسی می‌کند که بیت ۱ شماره‌شان یک است: ۱، ۳، ۵، ۷.
    • p2 موقعیت‌های ۲، ۳، ۶، ۷.
    • p4 موقعیت‌های ۴، ۵، ۶، ۷.

    تشخیص و تصحیح

    گیرنده هر سه بررسی را دوباره حساب می‌کند. اگر بیت موقعیت k خراب شده باشد، دقیقاً بررسی‌هایی ناموفق می‌شوند که k را پوشش می‌دهند، یعنی بیت‌های شماره‌ی k. پس عدد دودویی بررسی‌های ناموفق (نشانگر) همان k است و بیت را برمی‌گردانیم. نشانگر صفر یعنی خطایی نیست.

    این کد هر خطای تک‌بیتی را درست می‌کند ولی دو خطا را نه.

    در trace به چه چیزی نگاه کنی

    • جدول نام هر موقعیت و بیتش را نشان می‌دهد؛ ببین کدام بیت خراب و دوباره درست می‌شود.