کدهای گروهی

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

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

قضایا 
 در کدگروهی، مینیمم فاصله بین کدواژه ها، مینیمم وزن عنصرهای غیر صفر کد است.
بدین ترتیب محاسبه مینیمم فاصله بین کدواژه‌ها ساده‌تر است. 
مثلاً اگر C مجموعه‌ای از کدواژه‌های باشد که ۱۰۲۴=|C| باشد، برای یافتن مینیمم فاصله بین کدواژه‌ها مجبوریم ۵۲۳۷۷۶ = 
فاصله را محاسبه و بررسی کنیم، در حالی که اگر نشان دهیم C دارای ساختار گروهی است، کافیست ۱۰۲۳ عنصر غیر صفر آن را بررسی کنیم.
 برای تعیین سختار گروهی برای کدواژه‌ها از خواص هم ریختی استفاده می کنیم. بدین ترتیب که اگر
E : Z۲m→Z۲n
همریخت با گروهی باشد، آنگاه
C = E(Zm۲)۰ 
زیر گروهی از 
Zn۲
است.
 فرض کنیدE : Zm۲→Zn۲یک تابع کدگذاری باشد که به وسیله ماتریس مولد G یا ماتریس بررسی زوجیت H داده شده‌است. در این صورتC = E(Zm۲)۰ یک کد گروهی است.
 مشاهده می‌شود که اگرx,y∈Zm۲آنگاهE(x+y) = (x+y)G = xG + yG = E(x) + E(y)۰ بنابراین، E همریختی است وC = E(Zm۲)۰ یک کدگروهی است.
 برای حالت H، اگر x یک پیام باشد، آنگاه E(x) = x۱x۲...sm<...xn و 
x= x۱x۲...sm< ∈Zm۲ و . H.(E(X))tr =۰ به خصوص، E(x)۰ بنابراین دو ویژگی به صورتی یکتا تعیین می‌شوند. اگر y نیز پیامی باشد، آنگاه x+y نیز یک پیام است و m مؤلفه اول E(x+y)۰ نظیر مورد E(x)+E(y)۰  عبارت است از(x۱+y۱)،(x۲+y۲)،...،(xm+ym)
به علاوه داریم
H.(E(x)+E(y))tr = H.(E(x)tr+E(y)tr) = H.E(x)tr+ H.E(y)tr = ۰+۰=۰
 چون E(x+y)۰ عنصر یکتای Zn۲، با m مؤلفه اول (x۱+y۱)،(x۲+y۲)،...،(xm+ym) و با H.(E(x)+E(y))tr = ۰است، از این جا نتیجه می‌شود که E(x+y)= E(x)+E(y)۰ پس E یک هم ریختی گروهی است و C = {c∈Zm۲|H.ctr = ۰}۰ یک کد گروهی است.

کدگشایی با پیشروهای هم مجموعه‌ای 
برای تهیه الگویی برای کدگشایی، ساختار گروهی C را، همراه با هم مجموعه‌هایش در 
به کار می بریم. برای این منظور مراحل زیر را طی می کنیم:
 ضمن شروع با هنصر همانی، عنصرهای کد گروهی C را در سطری فهرست می کنیم.
 سپس عنصر x از Zn۲را چنان برمی گزینیم که در هیچ جای جدولی که تا اینجا درست کرده ایم ذکر نشده باشد و دارای وزن مینیمم باشد. سپس هناصر هم مجموعه x+C با x+c را مستقیما زیر c به ازای هر c∈C ثبت می کنیم.
 گام ۲ را تا وقتی هم مجموعه‌ها افرازی از Zn۲ به دست دهند، تکرار می کنیم. این نتایج در جدولی موسوم به جدول کدگشایی گردآوری می‌شوند.
 در این جدول، برای هر واژه دریافتی r، ستونی را به دست می آوریم که شامل r است و سه مؤلفه اول کدواژه c در بالای ستون را برای کدگشای r به کار می بریم.
درایه‌های اولین ستون جدول کدگشایی را پیشروهای هم مجموعه می نامند. البته باید دقت شود با توجه به این که در هر مرحله لزوما کدواژه با کمترین وزن یکتا نیست، شمایل جدول نیز یکتا نخواهد بود.
جدول زیر با اعمال روش بالا به تابع کدگذاری 
E : Z۳۲→Z۶۲
است با تعریف روبرو بدست می‌آید:

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

بدین ترتیب برای واژه‌های دریافتی 
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⊇Zn۲ کدی گروهی برای ماتریس بررسی زوجیت H باشد و r۱,r۲∈Zn۲ برای جدول هم مجموعه‌های C در Zm۲ ، 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.xtr+ H.(c۱)tr = H.xtr+۰=H.xtr

زیراc۱ کدواژه است. همچنین H.(r۱)tr = H.xtr
پس نشانگان یکی است. از طرف دیگر:

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 بیت است. این وضعیت چندان مطلوب نیست. برای این منظور جدول زیر را تشکیل می دهیم:

که در سمت راست هر سطر پیشروهای هم مجموعه نشانگان هر سطر آمده‌است.اینک با دریافت واژه r با شیوه زیر اقدام به کدگشایی آن می کنیم:
 نشانگان H.rtr را حساب می کنیم.
 پیشرو هممجموعه x را در سمت چپ H.rtr پیدا می کنیم.
 x را به r اضافه می کنیم تا c را بدست آوریم. (کدواژه c در دو رابطه  x = c+r و c = x+r صدق می‌کند.)
در نتیجه از جدول بالا به دو ستون سمت راست احتیاج داریم. که در مجموع 72 بیت حافظه نیاز دارد و این عدد در مقابل 384 بیت پیشرفت قابل توجهی به‌شمار می‌رود.(البته باید 18 بیت مربوط به H را نیز در نظر بگیریم که در مجموع می‌شود 90 بیت).

این فرآیند را کدگشایی به وسیله پیشروهای هم مجموعه می گویند.
وقتی به وسیله پیشروهای هم مجموعه‌ای کدگشایی می کنیم، اگرr∈Z۲n
واژه باشد و از r به صورت کدواژه c*
کدگشایی شود، در این صورت برای همه کدواژه‌های c
داریم: d(c*,r) ≤ d(c,r)۰

منابع و مآخذ 

 

 

رمزنگاری