فهرست مقاله
در کدِ تصحیح خطا، برگرداندنِ یک خروجیِ ظاهراً معتبر همیشه به معنی بازیابیِ پیامِ فرستاده‌شده نیست. Hamming(7,4) مثال خوبی برای دیدنِ این فاصله است: چهار بیتِ داده را به هفت بیت تبدیل می‌کنیم و با فرضِ حداکثر یک بیتِ تغییرکرده، پیام را بازمی‌یابیم. سپس عمداً دو بیت را عوض می‌کنیم و می‌بینیم همان رمزگشا چگونه یک جوابِ معتبر اما غلط می‌سازد. این آزمایشِ دقیقِ نرم‌افزاری است؛ کانال، حافظه یا تجهیزاتِ مخابراتیِ واقعی آزمایش نمی‌شوند.
۱. هفت بیت و قرارداد جایگاه‌های زوجیت
جایگاه‌ها را از چپ به راست، از یک تا هفت شماره می‌زنیم. جایگاه‌های یک، دو و چهار برای بیت‌های بررسیِ زوجیت و جایگاه‌های سه، پنج، شش و هفت برای چهار بیتِ داده‌اند. اندیسِ داخلیِ فهرست پایتون از صفر شروع می‌شود؛ بنابراین جایگاه شش در قراردادِ مخابراتی، خانهٔ پنج در فهرست است. این دو شماره را در گزارش مخلوط نمی‌کنیم. رشتهٔ «۱۰۱۱» نیز خودکار به بیت تبدیل نمی‌شود؛ ورودی، list یا tuple با چهار عدد صحیحِ صفر یا یک است.
زوجیت را زوج می‌گیریم: مجموعِ بیت‌های هر گروه در حسابِ پیمانهٔ دو، صفر است. گروهِ بررسیِ اول جایگاه‌های یک، سه، پنج و هفت، گروهِ دوم دو، سه، شش و هفت و گروهِ سوم چهار، پنج، شش و هفت را می‌گیرد. جمعِ پیمانهٔ دو همان XOR بیت‌هاست؛ جمعِ معمولِ عددها بدون گرفتنِ باقیمانده، محاسبهٔ دیگری می‌سازد. ترتیبِ داده در چهار جایگاهِ آزاد نیز بخشی از قرارداد است.
یادداشتِ اصلیِ کدهای تصحیح خطای MIT، ساختارِ بررسیِ زوجیت با ستون‌های دودوییِ یک تا هفت را توضیح می‌دهد. ما برای دادهٔ (1,0,1,1)، بیت‌های بررسیِ صفر، یک و صفر را می‌سازیم؛ کلمهٔ نهایی 0110011 است. این مثالِ تألیفی را با رمزگذار و پاسخِ دستی می‌سنجیم و نمونه یا شکلِ منبع را بازنشر نمی‌کنیم.
۲. syndrome و فرضِ یک خطا
سه نتیجهٔ بررسیِ زوجیت را می‌توان به یک عددِ سه‌بیتی تبدیل کرد؛ نامش syndrome است. بیتِ بررسیِ گروهِ اول ارزشِ یک، گروهِ دوم ارزشِ دو و گروهِ سوم ارزشِ چهار دارد. وقتی فقط یک بیت عوض شده باشد، این عدد همان جایگاهِ خطاست. مثلاً خطای جایگاه شش، گروه‌های دوم و سوم را خراب می‌کند؛ مقدارِ حاصل دو به اضافهٔ چهار، یعنی شش است. صفر بودنِ syndrome تنها می‌گوید روابطِ زوجیت برقرارند.
بخشِ کاملِ Hamming در درسِ 6.02 MIT، صفحه‌های ۱۲ تا ۱۴ جدولِ همین نگاشت و ترتیبِ جایگاه‌ها را نشان می‌دهد. مسیرِ اصلیِ ما به‌جای سه حلقهٔ گروه، شمارهٔ تمام جایگاه‌هایی را که بیتشان یک است XOR می‌کند. ستون‌های بررسی همان شماره‌ها در نمایشِ دودویی‌اند، پس نتیجه با سه بررسی برابر است. این ساده‌سازی به همین چیدمان وابسته است؛ برای کلمه‌ای با ترتیبِ متفاوت، نباید شمارهٔ خام را بی‌تغییر استفاده کرد.
رمزگشا در syndrome غیرصفر، بیتِ معرفی‌شده را برمی‌گرداند. نامِ عملِ خروجی صریحاً می‌گوید «تغییر بیت تحت فرضِ خطای تکی». آن را گزارشِ قطعیِ یک خطای مشاهده‌شده نمی‌نامیم. در syndrome صفر نیز پیامِ «بررسی‌های زوجیت برقرار است» می‌دهیم، نه «انتقال بدون خطا بوده است». مدلِ مسئله، حداکثر یک تغییرِ بیتی برای بازیابیِ درست است؛ حذفِ بیت، جابه‌جاییِ طول، پاک‌شدگیِ جایگاه و لغزشِ هم‌زمان‌سازی بیرونِ این قراردادند.
۳. کد کاملِ کدگذار و رمزگشا
فایل hamming74_syndrome.py با Python 3.14.5 و فقط کتابخانهٔ استاندارد اجرا شده است. فرمانِ بازسازی python hamming74_syndrome.py است. طولِ چهار و هفت، محدودیتِ دلخواه برای کوچک کردنِ ورودی نیست؛ اندازهٔ خودِ کدِ Hamming(7,4) است. bool، float، زیرکلاسِ عدد صحیح، مقدارِ دو، رشته و طولِ ناسازگار رد می‌شوند. هیچ بایتی به بیت شکسته و هیچ ترتیبِ بیتِ شبکه‌ای از روی رشته حدس زده نمی‌شود.
"""Even-parity Hamming(7,4), with explicit single-error assumption."""
from dataclasses import asdict, dataclass
from itertools import combinations, product
import json
import platform
DATA_POSITIONS = (3, 5, 6, 7) # one-based, left to right
def bits(value, length):
if type(value) not in (list, tuple) or len(value) != length:
raise ValueError('wrong bit sequence container or length')
if any(type(x) is not int or x not in (0, 1) for x in value):
raise ValueError('each bit must be an exact integer zero or one')
return tuple(value)
def encode(data):
d1, d2, d3, d4 = bits(data, 4)
return (d1 ^ d2 ^ d4, d1 ^ d3 ^ d4, d1,
d2 ^ d3 ^ d4, d2, d3, d4)
def syndrome(received):
word = bits(received, 7)
result = 0
for position, bit in enumerate(word, start=1):
if bit:
result ^= position
return result
@dataclass(frozen=True)
class Decoded:
received: tuple
input_syndrome: int
output_word: tuple
data: tuple
action: str
def decode(received):
word = bits(received, 7)
s = syndrome(word)
corrected = list(word)
if s:
corrected[s - 1] ^= 1
corrected = tuple(corrected)
action = ('bit_flipped_under_single_error_assumption' if s
else 'parity_checks_satisfied_not_proof_of_no_errors')
return Decoded(word, s, corrected,
tuple(corrected[p - 1] for p in DATA_POSITIONS), action)
def independent_codebook():
# Literal parity-check rows, using dot products modulo two, not encode/XOR.
rows = ((1, 0, 1, 0, 1, 0, 1),
(0, 1, 1, 0, 0, 1, 1),
(0, 0, 0, 1, 1, 1, 1))
return tuple(w for w in product((0, 1), repeat=7)
if all(sum(a * b for a, b in zip(row, w, strict=True)) % 2 == 0
for row in rows))
def nearest_codeword(received, codebook):
distances = [(sum(a != b for a, b in zip(received, w, strict=True)), w)
for w in codebook]
minimum = min(d for d, _ in distances)
winners = [w for d, w in distances if d == minimum]
assert len(winners) == 1
return winners[0], minimum
def flip(word, positions):
changed = list(word)
for position in positions:
changed[position - 1] ^= 1
return tuple(changed)
def rejected(function, value):
try:
function(value)
except ValueError:
return True
return False
def main():
data = (1, 0, 1, 1)
word = encode(data)
single = decode(flip(word, (6,)))
double = decode(flip(word, (1, 2)))
book = independent_codebook()
checks = {}
checks['literal_hand_codeword'] = word == (0, 1, 1, 0, 0, 1, 1)
checks['literal_single_position_six_recovery'] = (
single.input_syndrome == 6 and single.output_word == word and single.data == data)
checks['independent_codebook_has_16_unique_data_messages'] = (
len(book) == 16 and len({(w[2], w[4], w[5], w[6]) for w in book}) == 16)
recovery_cases = 0
for message in product((0, 1), repeat=4):
encoded = encode(message)
assert encoded in book
for location in range(8):
received = encoded if location == 0 else flip(encoded, (location,))
result = decode(received)
expected, distance = nearest_codeword(received, book)
assert result.output_word == expected == encoded
assert result.data == message and result.input_syndrome == location
assert distance == int(location != 0)
recovery_cases += 1
checks['all_16_messages_times_8_no_or_single_error_cases_one_group'] = recovery_cases == 128
whole_space = 0
for received in product((0, 1), repeat=7):
nearest, distance = nearest_codeword(received, book)
assert distance <= 1 and decode(received).output_word == nearest
whole_space += 1
checks['all_128_received_words_unique_nearest_codeword_one_group'] = whole_space == 128
distances = [sum(a != b for a, b in zip(x, y, strict=True))
for x, y in combinations(book, 2)]
checks['independent_minimum_code_distance_three'] = min(distances) == 3
double_cases = 0
for original in book:
for pair in combinations(range(1, 8), 2):
result = decode(flip(original, pair))
assert result.input_syndrome != 0
assert result.output_word in book and result.output_word != original
assert syndrome(result.output_word) == 0
double_cases += 1
checks['all_336_double_errors_miscorrect_under_single_error_decoder_one_group'] = double_cases == 336
checks['literal_double_error_witness'] = (
double.input_syndrome == 3 and double.output_word == (1, 0, 0, 0, 0, 1, 1)
and double.data == (0, 0, 1, 1) and double.data != data)
triple = flip((0,) * 7, (1, 2, 3))
checks['zero_syndrome_can_hide_three_changes'] = (
syndrome(triple) == 0 and triple != (0,) * 7 and decode(triple).data == (1, 0, 0, 0))
linear_cases = 0
for a, b in product(tuple(product((0, 1), repeat=4)), repeat=2):
assert encode(tuple(x ^ y for x, y in zip(a, b, strict=True))) == tuple(
x ^ y for x, y in zip(encode(a), encode(b), strict=True))
linear_cases += 1
checks['all_256_message_pairs_linear_xor_one_group'] = linear_cases == 256
data_list, word_list = list(data), list(word)
list_encoded, list_decoded = encode(data_list), decode(word_list)
checks['list_inputs_are_accepted_without_mutating_them'] = (
list_encoded == word and list_decoded.data == data
and data_list == list(data) and word_list == list(word))
checks['container_and_length_rejections'] = (
all(rejected(encode, x) for x in ((), (0,) * 3, (0,) * 5, '1011', None))
and all(rejected(decode, x) for x in ((), (0,) * 6, (0,) * 8, '0110011', None)))
class IntChild(int):
pass
checks['exact_bit_type_and_binary_value_rejections'] = all(
rejected(encode, (bad, 0, 0, 0)) and rejected(decode, (bad,) + (0,) * 6)
for bad in (True, 1.0, IntChild(1), -1, 2, '1', complex(1)))
assert all(type(value) is bool and value for value in checks.values())
print(json.dumps({
'python': platform.python_version(), 'dependencies': 'stdlib only',
'bit_positions': 'one-based left-to-right, even parity at 1,2,4; data at 3,5,6,7',
'hand_data': data, 'hand_word': word, 'hand_single_position_6': asdict(single),
'hand_double_positions_1_2': asdict(double),
'code_rate_fraction': '4/7', 'minimum_code_distance': min(distances),
'no_or_single_error_cases_inside_one_group': recovery_cases,
'double_error_cases_inside_one_group': double_cases,
'whole_received_space_inside_one_group': whole_space,
'checks': checks, 'unique_check_groups': len(checks), 'all_passed': True,
'limits': 'Correct recovery requires at most one flipped bit. This decoder cannot distinguish a single error from a double-error syndrome; no SECDED, erasures, bursts, byte framing or hardware reliability measurement.'
}, ensure_ascii=False, indent=2))
if __name__ == '__main__':
main()
خروجی، کلمهٔ دریافت‌شده، syndrome ورودی، کلمهٔ پس از عمل، دادهٔ استخراج‌شده و نامِ عمل را نگه می‌دارد. اگر فقط دادهٔ چهار‌بیتی را پس بدهیم، تشخیصِ فرضِ اعمال‌شده و بازبینیِ تغییرِ بیت دشوارتر می‌شود. تابع‌ها ورودیِ فهرستی را تغییر نمی‌دهند و نتیجه‌ها تاپل و رکوردِ frozen هستند. این ویژگی، امنیتِ حافظه یا تضمینِ اجرای هم‌زمانِ یک گیرنده نیست؛ فقط رفتارِ رابطِ همین محاسبه را مشخص می‌کند.
از کلمهٔ 0110011، بیتِ جایگاه شش را از یک به صفر عوض می‌کنیم؛ دریافت 0110001 است. syndrome شش می‌شود، همان بیت برمی‌گردد و داده دوباره 1011 است. بیت‌های زوجیت هم می‌توانند خراب شوند؛ آزمون‌ها فقط چهار بیتِ داده را هدف نمی‌گیرند. در بازیابیِ تک‌خطا، هفت جایگاه باید به یک اندازه در پوششِ بررسی باشند.
۴. مرجع کتابچهٔ کد و شاهدِ دو خطا
مرجع مستقل، رمزگذار یا تابعِ syndrome را برای ساختِ انتظار فراخوانی نمی‌کند. همهٔ ۱۲۸ دنبالهٔ هفت‌بیتی را می‌سازد و با ضربِ داخلیِ سه سطرِ صریحِ بررسی، کلمه‌های مجاز را جدا می‌کند. شانزده کلمه باقی می‌ماند و چهار جایگاهِ داده، هر شانزده پیامِ ممکن را دقیقاً یک بار نشان می‌دهند. سپس برای هر ورودی، فاصلهٔ Hamming تا همهٔ کلمه‌های مجاز، یعنی تعداد جایگاه‌های متفاوت، شمرده می‌شود. نزدیک‌ترین کلمهٔ یکتا، جوابِ مرجع است.
برای شانزده پیام، حالتِ بدون تغییر و هر هفت تغییرِ تکی، ۱۲۸ مقایسه در یک گروه می‌سازند. وارسیِ کلِ فضای دریافت هم نشان می‌دهد هر دنباله به یک کلمه در فاصلهٔ حداکثر یک نزدیک است؛ این ویژگی، فرضِ خطای تکی را ثابت نمی‌کند. کمترین فاصلهٔ دو کلمهٔ معتبر سه است. بنابراین یک دریافتِ حاصل از دو خطا می‌تواند به کلمهٔ معتبرِ دیگری نزدیک‌تر از پیامِ واقعی باشد؛ برگشتنِ جوابِ معتبر، شاهدِ کافی برای بازیابی نیست.
{
"python": "3.14.5",
"dependencies": "stdlib only",
"bit_positions": "one-based left-to-right, even parity at 1,2,4; data at 3,5,6,7",
"hand_data": [
1,
0,
1,
1
],
"hand_word": [
0,
1,
1,
0,
0,
1,
1
],
"hand_single_position_6": {
"received": [
0,
1,
1,
0,
0,
0,
1
],
"input_syndrome": 6,
"output_word": [
0,
1,
1,
0,
0,
1,
1
],
"data": [
1,
0,
1,
1
],
"action": "bit_flipped_under_single_error_assumption"
},
"hand_double_positions_1_2": {
"received": [
1,
0,
1,
0,
0,
1,
1
],
"input_syndrome": 3,
"output_word": [
1,
0,
0,
0,
0,
1,
1
],
"data": [
0,
0,
1,
1
],
"action": "bit_flipped_under_single_error_assumption"
},
"code_rate_fraction": "4/7",
"minimum_code_distance": 3,
"no_or_single_error_cases_inside_one_group": 128,
"double_error_cases_inside_one_group": 336,
"whole_received_space_inside_one_group": 128,
"checks": {
"literal_hand_codeword": true,
"literal_single_position_six_recovery": true,
"independent_codebook_has_16_unique_data_messages": true,
"all_16_messages_times_8_no_or_single_error_cases_one_group": true,
"all_128_received_words_unique_nearest_codeword_one_group": true,
"independent_minimum_code_distance_three": true,
"all_336_double_errors_miscorrect_under_single_error_decoder_one_group": true,
"literal_double_error_witness": true,
"zero_syndrome_can_hide_three_changes": true,
"all_256_message_pairs_linear_xor_one_group": true,
"list_inputs_are_accepted_without_mutating_them": true,
"container_and_length_rejections": true,
"exact_bit_type_and_binary_value_rejections": true
},
"unique_check_groups": 13,
"all_passed": true,
"limits": "Correct recovery requires at most one flipped bit. This decoder cannot distinguish a single error from a double-error syndrome; no SECDED, erasures, bursts, byte framing or hardware reliability measurement."
}در شاهدِ دوخطا، جایگاه‌های یک و دو را عوض می‌کنیم. دریافت 1010011 و syndrome سه است؛ رمزگشا بیتِ سوم را هم تغییر می‌دهد و 1000011 می‌سازد. دادهٔ خروجی 0011 است، نه دادهٔ اصلی. در تمام ۳۳۶ حالتِ دو تغییرِ متمایز روی شانزده کلمه، همین رمزگشای تک‌خطا به کلمهٔ دیگری رفت. هر مجموعه یک گروه است؛ مجموعِ سیزده گروهِ نام‌دار را با تعداد حالت‌های درونشان جمع نمی‌زنیم.
۵. چهار پرسش و مرز SEC
پرسش اول: نرخِ این کد چقدر است؟ پاسخ: چهار بیتِ داده در هفت بیتِ کلمه داریم؛ نرخِ کد ۴/۷ و افزوده نسبت به داده سه‌چهارم است. این نسبت‌ها نرخِ مفیدِ یک شبکهٔ واقعی نیستند؛ سربرگ، ارسالِ مجدد و مدلِ کانال در مثال وجود ندارند.
پرسش دوم: آیا دو تغییر اصلاً دیده نمی‌شوند؟ پاسخ: بررسیِ زوجیت برای دو تغییرِ متمایز، syndrome غیرصفر می‌دهد؛ اما همان نشانه می‌تواند از یک تغییر آمده باشد. مشکلِ این رمزگشای تصحیح‌کننده، جدا نکردنِ دوخطا از تک‌خطاست. پس توانِ تشخیصِ نقضِ زوجیت را با قابلیتِ هم‌زمانِ تصحیحِ تکی و اعلامِ دوخطایی یکی نمی‌گیریم.
پرسش سوم: syndrome صفر، نبودِ هر خطایی را ثابت می‌کند؟ پاسخ: خیر؛ از کلمهٔ تمام‌صفر، تغییرِ جایگاه‌های یک، دو و سه، کلمهٔ معتبرِ دیگری با syndrome صفر می‌سازد. برای SECDED به کدِ گسترش‌یافته و قواعدِ مناسبِ رمزگشایی نیاز است؛ این برنامه آن را پیاده نمی‌کند.
پرسش چهارم: این محاسبه جای CRC یا مرزبندی پیام را می‌گیرد؟ پاسخ: خیر؛ قراردادِ پذیرش با CRC هدف و پارامترهای دیگری دارد و مرزبندی جریان بایت هنوز مسئولیتِ جداست. منابع در ۲۶ مهر ۱۴۰۵ خوانده شدند؛ ترمِ ۲۰۰۷ و تاریخِ بازنگریِ ۲۷ سپتامبر ۲۰۱۰ اطلاعاتِ منابع‌اند، نه تاریخِ خبرِ تازه. این مثال احتمالِ خطای کانال، اصالتِ فرستنده یا قابلیتِ اتکایِ سخت‌افزار را اندازه نمی‌گیرد.
منابع و مطالعهٔ بیشتر
بررسی منابع: ۲۶ مهر ۱۴۰۵. تحلیل‌ها و پیشنهادهای اجرایی، جمع‌بندی نویسنده‌اند.
