کدهای گروهی

زمانی که صحبت از انتقال اطلاعات به میان می‌آید، رمزنگاری نقش مهمی ایفا می‌کند. معمولا در رمزنگاری علاقمند به حفظ سلامت و امنیت اطلاعات هستیم. از این رو روشهایی که امکان تصحیح خطا را فراهم می‌کنند و همچنین قابل بازیابی نیستند. چنین روش‌هایی معمولا سنگین ترند و حچم داده بیشتری منتقل می‌کنند در نتیجه کند‌تر هستند و گران‌تر. معمولا در یک انتخاب بین امنیت و هزینه انتقال اطلاعات هستیم. برای بحث بیشتر می‌توانید به مباحث تخصصی موجود مراجعه کنید.
به هر حال مبانی رمزنگاری و کدگذاری خارج از این بحث است و این نوشتار تنها به بحث ریاضی حول توابع کدگذاری است که حافظ ساختار گروه هستند.
کدهای گروهی
درصورتی که
E : Z m ۲ →Z n ۲
یک تابع کدگذاری باشد، کد C = E(Z m ۲ )۰ را کد گروهی می‌نامند اگر C زیر گروه
Z n ۲
باشد.
قضایا
در کدگروهی، مینیمم فاصله بین کدواژه‌ها، مینیمم وزن عنصرهای غیر صفر کد است.
بدین ترتیب محاسبه مینیمم فاصله بین کدواژه‌ها ساده‌تر است.
مثلا اگر C مجموعه‌ای از کدواژه‌های باشد که ۱۰۲۴=|C| باشد، برای یافتن مینیمم فاصله بین کدواژه‌ها مجبوریم ۵۲۳۷۷۶ =
فاصله را محاسبه و بررسی کنیم، در حالی که اگر نشان دهیم C دارای ساختار گروهی است، کافیست ۱۰۲۳ عنصر غیر صفر آن را بررسی کنیم.
برای تعیین سختار گروهی برای کدواژه‌ها از خواص هم ریختی استفاده می‌کنیم. بدین ترتیب که اگر
E : Z ۲ m →Z ۲ n
همریخت با گروهی باشد، آنگاه
C = E(Z m ۲ )۰
زیر گروهی از
Z n ۲
است.
فرض کنیدE : Z m ۲ →Z n ۲ یک تابع کدگذاری باشد که به وسیله ماتریس مولد 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 n ۲ ، با 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 را، همراه با هم مجموعه‌هایش در
به کار می‌بریم. برای این منظور مراحل زیر را طی می‌کنیم:
ضمن شروع با هنصر همانی، عنصرهای کد گروهی C را در سطری فهرست می‌کنیم.
سپس عنصر x از Z n ۲ را چنان برمی گزینیم که در هیچ جای جدولی که تا اینجا درست کرده‌ایم ذکر نشده باشد و دارای وزن مینیمم باشد. سپس هناصر هم مجموعه x+C با x+c را مستقیما زیر c به ازای هر c∈C ثبت می‌کنیم.
گام ۲ را تا وقتی هم مجموعه‌ها افرازی از Z n ۲ به دست دهند، تکرار می‌کنیم. این نتایج در جدولی موسوم به جدول کدگشایی گردآوری می‌شوند.
در این جدول، برای هر واژه دریافتی 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
\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 n ۲ کدی گروهی برای ماتریس بررسی زوجیت H باشد و r ۱ ,r ۲ ∈Z n ۲ برای جدول هم مجموعه‌های 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
\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 با شیوه زیر اقدام به کدگشایی آن می‌کنیم:
نشانگان H.r tr را حساب می‌کنیم.
پیشرو هممجموعه x را در سمت چپ H.r tr پیدا می‌کنیم.
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)۰
منابع و مآخذ