کدهای گروهی

زمانی که صحبت از انتقال اطلاعات به میان می‌آید، رمزنگاری نقش مهمی ایفا می‌کند. معمولاً در رمزنگاری علاقمند به حفظ سلامت و امنیت اطلاعات هستیم. از این رو روشهایی که امکان تصحیح خطا را فراهم می‌کنند و همچنین قابل بازیابی نیستند. چنین روش‌هایی معمولاً سنگین ترند و حچم داده بیشتری منتقل می‌کنند در نتیجه کند تر هستند و گران تر. معمولاً در یک انتخاب بین امنیت و هزینه انتقال اطلاعات هستیم. برای بحث بیشتر می‌توانید به مباحث تخصصی موجود مراجعه کنید. به هر حال مبانی رمزنگاری و کدگذاری خارج از این بحث است و این نوشتار تنها به بحث ریاضی حول توابع کدگذاری است که حافظ ساختار گروه هستند.

کدهای گروهی

درصورتی که E : Z^m_۲→Zⁿ_۲ یک تابع کدگذاری باشد، کد C = E(Z^m_۲)۰ را کد گروهی می نامند اگر C زیر گروه Zⁿ_۲ باشد.

قضایا

• در کدگروهی، مینیمم فاصله بین کدواژه ها، مینیمم وزن عنصرهای غیر صفر کد است.

بدین ترتیب محاسبه مینیمم فاصله بین کدواژه‌ها ساده‌تر است.

مثلاً اگر C مجموعه‌ای از کدواژه‌های باشد که ۱۰۲۴=|C| باشد، برای یافتن مینیمم فاصله بین کدواژه‌ها مجبوریم ۵۲۳۷۷۶ = ${\binom {1024}{2}}$ فاصله را محاسبه و بررسی کنیم، در حالی که اگر نشان دهیم C دارای ساختار گروهی است، کافیست ۱۰۲۳ عنصر غیر صفر آن را بررسی کنیم.
برای تعیین سختار گروهی برای کدواژه‌ها از خواص هم ریختی استفاده می کنیم. بدین ترتیب که اگر E : Z_۲^m→Z_۲ⁿ همریخت با گروهی باشد، آنگاه C = E(Z^m_۲)۰ زیر گروهی از Zⁿ_۲ است.

• فرض کنیدE : Z^m_۲→Zⁿ_۲یک تابع کدگذاری باشد که به وسیله ماتریس مولد G یا ماتریس بررسی زوجیت H داده شده‌است. در این صورتC = E(Z^m_۲)۰ یک کد گروهی است.

مشاهده می‌شود که اگرx,y∈Z^m_۲آنگاهE(x+y) = (x+y)G = xG + yG = E(x) + E(y)۰ بنابراین، E همریختی است وC = E(Z^m_۲)۰ یک کدگروهی است.

برای حالت H، اگر x یک پیام باشد، آنگاه E(x) = x_۱x_۲...s_m<...x_n و

x= x_۱x_۲...s_m< ∈Z^m_۲ و . H.(E(X))_tr =۰ به خصوص، E(x)۰ بنابراین دو ویژگی به صورتی یکتا تعیین می‌شوند. اگر y نیز پیامی باشد، آنگاه x+y نیز یک پیام است و m مؤلفه اول E(x+y)۰ نظیر مورد E(x)+E(y)۰ عبارت است از(x_۱+y_۱)،(x_۲+y_۲)،...،(x_m+y_m) به علاوه داریم

H.(E(x)+E(y))^tr = H.(E(x)^tr+E(y)^tr) = H.E(x)^tr+ H.E(y)^tr = ۰+۰=۰

چون E(x+y)۰ عنصر یکتای Zⁿ_۲، با m مؤلفه اول (x_۱+y_۱)،(x_۲+y_۲)،...،(x_m+y_m) و با H.(E(x)+E(y))^tr = ۰است، از این جا نتیجه می‌شود که E(x+y)= E(x)+E(y)۰ پس E یک هم ریختی گروهی است و C = {c∈Z^m_۲|H.c^tr = ۰}۰ یک کد گروهی است.

کدگشایی با پیشروهای هم مجموعه‌ای

برای تهیه الگویی برای کدگشایی، ساختار گروهی C را، همراه با هم مجموعه‌هایش در به کار می بریم. برای این منظور مراحل زیر را طی می کنیم:

1. ضمن شروع با هنصر همانی، عنصرهای کد گروهی C را در سطری فهرست می کنیم.
2. سپس عنصر x از Zⁿ_۲را چنان برمی گزینیم که در هیچ جای جدولی که تا اینجا درست کرده ایم ذکر نشده باشد و دارای وزن مینیمم باشد. سپس هناصر هم مجموعه x+C با x+c را مستقیما زیر c به ازای هر c∈C ثبت می کنیم.
3. گام ۲ را تا وقتی هم مجموعه‌ها افرازی از Zⁿ_۲ به دست دهند، تکرار می کنیم. این نتایج در جدولی موسوم به جدول کدگشایی گردآوری می‌شوند.
4. در این جدول، برای هر واژه دریافتی r، ستونی را به دست می آوریم که شامل r است و سه مؤلفه اول کدواژه c در بالای ستون را برای کدگشای r به کار می بریم.

درایه‌های اولین ستون جدول کدگشایی را پیشروهای هم مجموعه می نامند. البته باید دقت شود با توجه به این که در هر مرحله لزوما کدواژه با کمترین وزن یکتا نیست، شمایل جدول نیز یکتا نخواهد بود.

جدول زیر با اعمال روش بالا به تابع کدگذاری E : Z^۳_۲→Z^۶_۲ است با تعریف روبرو بدست می‌آید:

$E(w)=w.{\begin{bmatrix}1&0&0&1&1&0\\0&1&0&0&1&1\\0&0&1&1&0&1\end{bmatrix}}$ ${\begin{array}{|c|c|c|c|c|c|c|c|c|}\\\hline 111000&011110&101011&110101&001101&010011&100110&000000\\011000&111110&001011&010101&101101&110011&000110&100000\\101000&001110&111011&100101&011101&000011&110110&010000\\110000&010110&100011&111101&000101&011011&101110&001000\\111100&011010&101111&110001&001001&010111&100010&000100\\111010&011100&101001&110111&001111&010001&100100&000010\\111001&011111&101010&110100&001100&010010&100111&000001\\101100&001010&111111&100001&011001&000111&110010&010100\\\end{array}}$

و ماتریس H که ترانهاده بخش بخش G است را چنین در می یابیم:

$H={\begin{bmatrix}1&0&1&1&0&0\\1&1&0&0&1&0\\0&1&1&0&0&1\end{bmatrix}}$

بدین ترتیب برای واژه‌های دریافتی r_۱ = 101001, r_۲ = 111010, r_۳ = 001001, r_۴ = 111011 کدواژه‌های زیر معتبر خواهند بود c_۱ = 101001, c_۲ = 111010, c_۳ = 001001, c_۴ = 111011 و پیام‌های زیر بدست می آیند:

w_۱ = 101, w_۲ = 111, w_۳ = 001, w_۴ = 101

• در صورتی که C⊇Zⁿ_۲ کدی گروهی برای ماتریس بررسی زوجیت H باشد و r_۱,r_۲∈Zⁿ_۲ برای جدول هم مجموعه‌های C در Z^m_۲ ، r_۱ ،

r_۲ در یک هم مجموعه C هستند اگر و تنها اگر H.(r_۱)^tr = H.(r_۲)^tr در واقع اگرr_۱ و r_۲ در یک هم مجموعه باشند، آن گاه r_۱ = x + c_۱ و r_۲ = x + c_۲ که در آن x پیشرو هم مجموعه‌ای است و c_۱و c_۲ کدواژه‌های واقع در بالای ستون‌های مربوط به r_۱ و r_۲هستند، در این صورت :

H.(r_۱)^tr = H.(x + c_۱)^tr = H.x^tr+ H.(c_۱)^tr = H.x^tr+۰=H.x^tr

زیراc_۱ کدواژه است. همچنین H.(r_۱)^tr = H.x^tr پس نشانگان یکی است. از طرف دیگر:

H.(r_۱)^tr = H.(r_۲)^tr => H.(r_۱ + r_۲)^tr = ۰ => r_۱ + r_۲

یک کدواژه c است. پس r_۱ + r_۲ = c لذا r_۱ = r_۲ + c و r_۱ ∈ r_۲ + C چون r_۲ ∈ r_۲ + C داریم که r_۱ و r_۲ در یک هم مجموعه‌اند. در این روش کدگشایی برای یافتن یک واژه باید تمام درایه‌های جدول تهیه شده را بررسی کرد که در مثال یاد شده این تعداد به 64 می‌رسد. هم چنین در C⊆Z^۱۲_۲ باید 4096 رشته را بررسی کنیم. همچنین حجم بیت‌های ذخیره شده، در C⊆Z^۶_۲ برابر با 384 بیت و در C⊆Z^۱۲_۲ برابر با 49152 بیت است. این وضعیت چندان مطلوب نیست. برای این منظور جدول زیر را تشکیل می دهیم:

${\begin{array}{|c|c|c|c|c|c|c|c|c|c|}\\\hline 111000&011110&101011&110101&001101&010011&100110&000000&000\\011000&111110&001011&010101&101101&110011&000110&100000&110\\101000&001110&111011&100101&011101&000011&110110&010000&011\\110000&010110&100011&111101&000101&011011&101110&001000&101\\111100&011010&101111&110001&001001&010111&100010&000100&100\\111010&011100&101001&110111&001111&010001&100100&000010&010\\111001&011111&101010&110100&001100&010010&100111&000001&001\\101100&001010&111111&100001&011001&000111&110010&010100&111\\\end{array}}$

که در سمت راست هر سطر پیشروهای هم مجموعه نشانگان هر سطر آمده‌است.اینک با دریافت واژه r با شیوه زیر اقدام به کدگشایی آن می کنیم:

1. نشانگان H.r^tr را حساب می کنیم.
2. پیشرو هممجموعه x را در سمت چپ H.r^tr پیدا می کنیم.
3. x را به r اضافه می کنیم تا c را بدست آوریم. (کدواژه c در دو رابطه x = c+r و c = x+r صدق می‌کند.)

در نتیجه از جدول بالا به دو ستون سمت راست احتیاج داریم. که در مجموع 72 بیت حافظه نیاز دارد و این عدد در مقابل 384 بیت پیشرفت قابل توجهی به‌شمار می‌رود.(البته باید 18 بیت مربوط به H را نیز در نظر بگیریم که در مجموع می‌شود 90 بیت).

این فرآیند را کدگشایی به وسیله پیشروهای هم مجموعه می گویند.

• وقتی به وسیله پیشروهای هم مجموعه‌ای کدگشایی می کنیم، اگرr∈Z_۲ⁿ

واژه باشد و از r به صورت کدواژه c^* کدگشایی شود، در این صورت برای همه کدواژه‌های c داریم: d(c^*,r) ≤ d(c,r)۰

منابع و مآخذ

• رالف گریمالدی (۱۳۸۵)، ریاضیات گسسته و ترکیبیاتی از دیدگاه کاربردی جلد دوم، ترجمهٔ دکتر علی عمیدی، تهران: مرکز نشر دانشگاهی، شابک ۹۶۴-۰۱-۰۸۹۰-۱

• جین پل ترمبلی، مانوهر (۱۳۸۵)، ریاضیات گسسته و کاربرد آن در کامپیوتر (ساختمان گسسته)، ترجمهٔ محمدعلی اسلامی، تهران: ققنوس، شابک ۹۶۴-۳۱۱-۱۸۷-۳