ماتریس مولد در نظریه کدگذاری

ماتریس مولد چیست؟

در نظریه کدگذاری، ماتریس مولد ماتریسی است که سطرهای آن یک پایه برای یک کد خطی می‌سازند. به بیان ساده‌تر، همه کلمه‌کدهای آن کد از ترکیب‌های خطی سطرهای این ماتریس به دست می‌آیند؛ بنابراین، یک کد خطی همان فضای سطری ماتریس مولد آن است.

اصطلاح‌شناسی

اگر G یک ماتریس باشد، کلمه‌کدهای کد خطی C را با رابطه زیر تولید می‌کند:

w = sG

در این رابطه، w یک کلمه‌کد از کد خطی C و s هر بردار ورودی دلخواه است. در این قالب، هر دو بردار w و s به‌صورت بردار سطری در نظر گرفته می‌شوند.

یک ماتریس مولد برای یک کد خطی با نماد [n,k,d]_q نشان داده می‌شود. در این نماد:

• n طول هر کلمه‌کد است؛
• k تعداد بیت‌های اطلاعاتی، یا همان بُعد کد C به‌عنوان یک زیرفضای برداری است؛
• d حداقل فاصله کد است؛
• q اندازه میدان متناهی، یعنی تعداد نمادهای الفبای کد است. برای مثال، اگر q = 2 باشد، کد دودویی است.

تعداد بیت‌های افزوده یا بیت‌های افزونگی معمولاً با n - k نمایش داده می‌شود.

شکل استاندارد ماتریس مولد

شکل استاندارد یک ماتریس مولد به این صورت نوشته می‌شود:

G = [I_k | P]

در این نمایش، I_k ماتریس همانی k × k و P یک ماتریس k × (n - k) است. وقتی ماتریس مولد در شکل استاندارد قرار دارد، کد C در k مختصات نخست خود سیستماتیک است؛ یعنی بیت‌های اطلاعاتی مستقیماً در بخش آغازین کلمه‌کد دیده می‌شوند.

ساخت ماتریس کنترل توازن

از ماتریس مولد می‌توان برای ساخت ماتریس کنترل توازن یک کد استفاده کرد و برعکس. اگر ماتریس مولد G در شکل استاندارد باشد، یعنی:

G = [I_k | P]

آنگاه ماتریس کنترل توازن برای کد C برابر است با:

H = [-P^T | I_{n-k}]

در این رابطه، P^T ترانهاده ماتریس P است. این نتیجه از آنجا به دست می‌آید که ماتریس کنترل توازنِ کد C، در واقع ماتریس مولد کد دوگان C^⊥ است.

در این نمایش، G یک ماتریس k × n و H یک ماتریس (n - k) × n است.

کدهای معادل

دو کد C1 و C2 را معادل می‌نامند و آن را با نماد C1 ~ C2 نشان می‌دهند، اگر بتوان یکی را از دیگری با دو نوع تبدیل زیر به دست آورد:

1. جابجایی دلخواه مؤلفه‌ها؛
2. ضرب مستقل هر مؤلفه در یک عضو غیرصفر.

کدهای معادل حداقل فاصله یکسانی دارند.

ماتریس‌های مولد کدهای معادل نیز می‌توانند با عملیات مقدماتی زیر از یکدیگر به دست آیند:

• جابجایی سطر؛
• ضرب سطر در یک اسکالر غیرصفر؛
• جمع یک سطر با سطر دیگر؛
• جابجایی ستون؛
• ضرب ستون در یک اسکالر غیرصفر.

بنابراین، می‌توان روی ماتریس مولد G حذف گاوسی انجام داد. این کار به ما اجازه می‌دهد فرض کنیم ماتریس مولد در شکل استاندارد قرار دارد. دقیق‌تر اینکه برای هر ماتریس G می‌توان یک ماتریس وارون‌پذیر U پیدا کرد به‌طوری‌که UG کدی معادل با کد تولیدشده توسط G بسازد.

همچنین ببینید

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