ماتریس تایید تولید ماتریس کدهای بلوک

معرفی

شرح فرآیند ارتباطات دیجیتال

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

در مرحله بعد، اطلاعات فشرده می شود (کدگذاری منبع) و افزونگی پیام را به حداقل می رساند. کدگذاری منبع هزینه های انتقال و ذخیره اطلاعات را کاهش می دهد. پس از این، پیام باید از طریق یک کانال پر سر و صدا منتقل شود. برای اینکه پیام به صورت تحریف نشده به دست مصرف کننده برسد، از کدگذاری اطلاعاتی مقاوم در برابر نویز (کدگذاری کانال) استفاده می شود. در سمت مصرف کننده، اطلاعات رمزگشایی می شود. رمزگشای کانال خطاهای کلمه دریافتی را تصحیح می کند و رمزگشای منبع کلمه تصحیح شده را به فرمی قابل خواندن برای مصرف کننده تبدیل می کند.

وقتی در مورد کدهای کنترل خطا صحبت می کنیم، باید بین دو استراتژی برای استفاده از آنها تمایز قائل شویم.

1. تصحیح مستقیم خطا به دلیل افزونگی (Forward Error Correction - FEC).
2. تشخیص خطا با درخواست‌های بعدی برای ارسال مجدد اطلاعات دریافتی اشتباه (Automatic Repeat Request - ARQ).

هنگام انتخاب روش های رمزگذاری و رمزگشایی، ما توسط عوامل بسیاری هدایت می شویم که رابطه آنها در شکل ارائه شده است.

کل پیچیدگی شامل هزینه‌های سخت‌افزاری و نرم‌افزاری برای پیاده‌سازی رمزگذار و رمزگشا، هزینه ذخیره‌سازی و انتقال اطلاعات و غیره است. شدت جریان داده شامل انتقال اطلاعات مفید، بیت‌های چک و همچنین درخواست‌ها و تکرارها می‌شود. بلوک اطلاعات فردی برای این درخواست ها.

کد نویسی مقاوم در برابر نویز

اطلاعات کلی

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

• ذخیره اطلاعات در رسانه های با چگالی بالا (رسانه مغناطیسی، CD-ROM، DVD)؛
• انتقال داده با قدرت سیگنال محدود (ماهواره و اتصال تلفن همراه);
• انتقال اطلاعات از طریق کانال های پر سر و صدا (ارتباطات سیار، پرسرعت خطوط سیمارتباطات)؛
• کانال های ارتباطی با افزایش نیاز به قابلیت اطمینان اطلاعات ( شبکه های کامپیوتر، خطوط انتقال با فشرده سازی داده ها).

در تمامی موارد فوق از کدهای کنترل خطا استفاده می شود.

در نظر بگیریم ساده ترین مدلانتقال داده با استفاده از کدگذاری مقاوم در برابر نویز

اجازه دهید رمزگذار منبع به طور متوالی کلمات اطلاعاتی با طول ثابت را خروجی دهد. رمزگذار کانال هر کلمه اطلاعاتی u را با کلمه رمز v جایگزین می کند. فرستنده سیگنال های مربوط به کلمه رمز v را تولید می کند و آنها را به کانال ارسال می کند. گیرنده تولید می کند تبدیل معکوس، در نتیجه کلمه باینری دریافتی r به رمزگشا می رسد. رمزگشا کلمه دریافتی r را با همه رمزهای ممکن کد مورد استفاده مقایسه می کند. اگر کلمه r با یکی از کلمات رمز منطبق باشد، کلمه اطلاعاتی مربوطه برای مصرف کننده صادر می شود. اگر r با تمام کلمات رمز متفاوت باشد، یک خطای قابل تشخیص در کانال رخ داده است. هدف از استفاده از کدگذاری کانال دستیابی به تطابق بین ارسال شده است کلمه اطلاعاتی u و کلمه اطلاعاتی دریافتی u ».

از جانب از این توصیف 2 نتیجه می توان گرفت:

• اگر در حین انتقال از طریق یک کانال پر سر و صدا، یک کلمه رمز به کلمه رمز دیگری که با رمز ارسال شده مطابقت ندارد نگاشت شود، یک خطای غیرقابل کشف رخ می دهد. بیایید آن را خطای رمزگشایی باقیمانده بنامیم.
• لازم است کدهایی بسازید که ساختار ریاضی خاصی داشته باشند که تشخیص مؤثر و در برخی موارد تصحیح خطاهایی را که هنگام انتقال اطلاعات از طریق کانال ارتباطی رخ می دهد، ممکن می سازد.

کدهای بلوک خطی

یک خانواده مهم از کدها توسط کدهای بلوک باینری خطی تشکیل می شود. این کدها از این جهت قابل توجه هستند که با نمایش اطلاعات و کلمات کد در قالب بردارهای دودویی، می‌توان فرآیندهای رمزگذاری و رمزگشایی را با استفاده از جبر خطی توصیف کرد. در این حالت اجزای بردارها و ماتریس های ورودی نمادهای 0 و 1 هستند. عملیات بر روی مولفه های باینری طبق قوانین انجام می شود. مدول حسابی 2.

معروف ترین کد خطی، کد بلاک هامینگ است. شرح بیشتر کدهای بلوک خطی با استفاده از این کد به عنوان مثال انجام خواهد شد. به طور خاص، ما کد Hamming (7،4) را در نظر خواهیم گرفت.

یک رمزگذار کد بلوک دودویی (n، k) مجموعه ای از 2 کیلو کلمه اطلاعات باینری ممکن را در مجموعه ای از 2 k n-بعد کلمه رمز ترسیم می کند. در نظریه کدگذاری، همیشه یک تناظر یک به یک بین این مجموعه ها وجود دارد.

به جای k بیت از بردار اطلاعات، n بیت از بردار کد به کانال منتقل می شود. در این مورد، ما در مورد کدگذاری اضافی با نرخی صحبت می کنیم: R = n ⁄ k.

هرچه سرعت کمتر باشد، کد اضافی تر است و توانایی محافظت در برابر خطاها بیشتر می شود. با این حال، باید در نظر داشت که با افزایش افزونگی، هزینه های انتقال اطلاعات نیز افزایش می یابد.

شرح فرآیندهای رمزگذاری و رمزگشایی

ماده منبع برای ساخت ساختارهای کد یک فضای برداری باینری n بعدی است که در آن مدول عملیات حسابی 2 مشخص شده است.یک فضای خطی k بعدی حاوی 2 کیلو کلمه رمز در آن تعبیه شده است. کد C با استفاده از 2 k ترکیب از k بردارهای پایه مستقل خطی (g 1،…، g k) تشکیل می شود.

این بردارها ردیف های ماتریس مولد کد C را تشکیل می دهند.

برای کد C، یک کد دوگانه Cd وجود دارد به طوری که حاصل ضرب اسکالر هر جفت بردار، که یکی از آنها متعلق به فضای C و دیگری به فضای Cd است، همیشه برابر با صفر است. این بدان معناست که بردارهای کد C متعامد با بردارهای کد C هستند، از طرف دیگر، اگر بردار خاصی با تمام بردارهای کد C متعامد باشد، متعلق به کد C است و بالعکس. زیرفضای برداری دوگانه توسط n-k بردارهای پایه مستقل خطی "گسترش" یافته است (h 1،...، hn-k). این بردارها ردیف های ماتریس بررسی برابری را تشکیل می دهند.

بیایید نمونه ای از ماتریس های تولید و بررسی برابری کد هامینگ (7،4) را در نظر بگیریم:

یک ویژگی مهم باید توجه شود: هم مولد و هم ماتریس چک حاوی یک ماتریس هویت هستند. این ویژگی در فرآیندهای رمزگذاری و رمزگشایی استفاده می شود.

کد نویسی

کلمه رمز v و کلمه اطلاعاتی u با این رابطه مرتبط هستند:

که در آن G ماتریس مولد است که ساختار آن در بالا توضیح داده شد.

به عنوان مثال، بردار اطلاعات u = (1010) به صورت زیر به بردار کد نگاشت می شود:

به راحتی می توان دید که چهار بیت آخر بردار کد با بردار اطلاعات منطبق است. این ویژگی سیستماتیک بودن کد نام دارد.

کدهایی که در آنها می توان یک کلمه اطلاعاتی را مستقیماً از بردار کد متناظر آن استخراج کرد، سیستماتیک نامیده می شوند. ماتریس تولید هر کد سیستماتیک همیشه می تواند با مرتب کردن مجدد ستون ها به شکل کاهش یابد:

G k × n = (P k × (n − k) I k)،

جایی که I k ماتریس هویت بعد k×k است.

بنابراین، در بردار کد یک کد سیستماتیک همیشه امکان تشخیص اطلاعات و نمادهای تأیید وجود دارد.

در ادامه نقش کاراکترهای آزمایشی و کاربرد آنها به تفصیل توضیح داده خواهد شد.

رمزگشایی

وظیفه رمزگشا این است که با استفاده از ساختار کد، بر اساس کلمه دریافتی r، بردار اطلاعات ارسالی را بازیابی کند. برای کد همینگ (7، 4) که در بالا مورد بحث قرار گرفت، می‌توانیم الگوریتم تشخیص خطای زیر را پیشنهاد کنیم. از آنجایی که کد مورد بررسی سیستماتیک است، هر یک از سه علامت چک را از طریق نمادهای بردار اطلاعات بیان می کنیم:

V 0 = v 3 ⊕ v 5 ⊕ v 6
v 1 = v 3 ⊕ v 4 ⊕ v 5
v 2 = v 4 ⊕ v 5 ⊕ v 6

اگر خطایی در کانال رخ دهد، در بردار دریافتی r حداقل یکی از برابری ها برآورده نمی شود. اجازه دهید روابط آزمون به دست آمده را در قالب یک سیستم معادلات برای اجزای بردار r بنویسیم:

R 0 ⊕ r 3 ⊕ r 5 ⊕ r 6 = s 0
r 1 ⊕ r 3 ⊕ r 4 ⊕ r 5 = s 1
r 2 ⊕ r 4 ⊕ r 5 ⊕ r 6 = s 2

بنابراین، از سه ستون اول ماتریس مولد G سیستمی از سه معادله آزمایشی به دست آوردیم. اگر در سیستم معادلات حاصل حداقل یکی از مولفه ها (s 0, s 1, s 2) برابر با صفر نباشد، خطا در کانال رخ داده است.

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

H (n - k)× n = (I n - k P T k × (n - k)).

سپس می توان سیستم معادلات تست را به صورت نوشتاری نوشت

ناقل s معمولا سندرم نامیده می شود. بنابراین، اگر حداقل یکی از اجزای s برابر با صفر نباشد، خطا تشخیص داده می شود.

به عنوان مثال، رمزگشایی سندرمیک (7، 4) کد همینگ را در نظر بگیرید. هنگام انتقال یک کلمه اطلاعاتی u = (1010) از طریق یک کانال بدون نویز r = v = (0011010). ما می توانیم بررسی کنیم که در این مورد سندرم برابر با 0 است.

به عنوان مثال، اگر یک خطا در کلمه کد در موقعیت چهارم رخ دهد (r = (0010010))، آنگاه سندرم ردیف چهارم ماتریس بررسی انتقال یافته است.

پس از عبور از تمام موقعیت های ممکن یک خطا، دریافت می کنیم میز کاملسندرم های خطاهای منفرد - جدولی از مطابقت بین تعداد رقم اشتباه و سندرم حاصل.

می توانید متوجه این خطا در موقعیت i-ام شوید کلمه رمزمربوط به سندرمی است که توسط ستون چهارم ماتریس H تشکیل شده است. از آنجایی که تمام ستون های ماتریس متفاوت هستند، می توانیم از جدول سندرم ها برای تصحیح یک خطای منفرد معرفی شده توسط کانال استفاده کنیم.

انواع خطاها

کدهای بلوک خطی دارای 3 نوع خطا هستند:

1. خطای قابل تشخیص و تصحیح
   • این سندرم در جدول سندرم وجود دارد
   • رمزگشا خطا را تشخیص داده و تصحیح می کند و سپس کلمه صحیح را به گیرنده ارسال می کند
2. خطای قابل تشخیص
   • کلمه دریافتی با هیچ یک از کلمات رمز مطابقت ندارد
   • سندرم در جدول سندرم وجود ندارد
   • رمزگشا خطا را تشخیص داده و درخواستی برای ارسال مجدد کلمه اطلاعاتی ارسال می کند.
3. خطای ناشناخته
   • کلمه دریافتی با یکی از کلمات رمز مطابقت دارد (نه با کلمه رمز اصلی)
   • سندرم 0 است
   • رمزگشا خطا را تشخیص نمی دهد و یک پیام اطلاعاتی اشتباه به مصرف کننده می دهد

نتیجه

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

ادبیات

1. ورنر ام. مبانی کدگذاری. - M.: Tekhnosphere، 2004.
2. Bleikhut R. نظریه و عمل کدهای کنترل خطا. - م.: میر، 1365.

اولگ ریباک

در واقع یافتن توضیح کافی دشوار است. اغلب، نویسندگان تصور می‌کنند که خواننده از قبل چیزهای زیادی می‌داند و سعی نمی‌کنند نکات به ظاهر ساده‌ای را که حاوی اصل هستند توضیح دهند. خیلی خوشحالم که باهاش ​​برخورد کردم این مواد، چیزی را برای خودم روشن کردم.

کدهای خطی دارای ویژگی های زیر هستند:

از این همه کثرت 2 کاز میان کلمات رمز مجاز که یک گروه خطی را تشکیل می دهند، می توانیم زیر مجموعه هایی را انتخاب کنیم ککلماتی که خاصیت استقلال خطی دارند.

استقلال خطی به این معنی است که هیچ یک از کلمات موجود در زیرمجموعه ای از کلمات رمز مستقل خطی را نمی توان با جمع (با استفاده از یک عبارت خطی) هیچ کلمه دیگری در آن زیر مجموعه به دست آورد.

در عین حال، هر یک از رمزهای مجاز را می توان با جمع کردن برخی از کلمات مستقل خطی به دست آورد.

بنابراین، ساخت ترکیب کدهای خطی با عملیات خطی همراه است. برای انجام چنین عملیاتی استفاده از یک دستگاه محاسبه ماتریس به خوبی توسعه یافته راحت است.

برای تحصیلات nکلمات کد بیتی از کلمات رمزگذاری شده k-bit (کدگذاری) از ماتریسی به نام مولد استفاده می کنند.

ماتریس مولد با نوشتن کلمات مستقل خطی در ستون k به دست می آید.

اجازه دهید توالی اطلاعات رمزگذاری شده را مشخص کنیم ایکسو ما آن را به صورت یک ماتریس ردیف می نویسیم ||X||بعد، ابعاد، اندازه 1* ک، مثلا:

||X||=||11001||،جایی که k=5.

یکی از روش های ساخت ماتریس مولد به شرح زیر است: از ماتریس هویت ساخته می شود. ||من|| بعد، ابعاد، اندازه k*kو ماتریس ارقام اضافی (زیاد) که در سمت راست به آن اختصاص داده شده است ||MDR||ابعاد k*r.

که در آن در ک=4

این ساختار OM یک کد سیستماتیک ارائه می دهد.

روش ساخت ماتریس MDR در زیر مورد بحث قرار خواهد گرفت.

7.4 دستور کدگذاری

کلمه رمز KS با ضرب ماتریس توالی اطلاعات به دست می آید ||X||به ماتریس مولد ||OM||:

ضرب طبق قوانین ضرب ماتریس انجام می شود: (SO on SO)

فقط باید به یاد داشته باشید که اضافه کردن در اینجا ماژول 2 انجام می شود.

بیایید بگوییم ماتریس مولد

||OM||= 0010 011

و بردار ردیف توالی اطلاعات

از آنجایی که ماتریسی که باید ضرب شود فقط یک ردیف دارد، ضرب ساده شده است. در این مورد، شما باید ردیف های ماتریس ژنراتور را مطابقت دهید ||OM||بیت های ماتریس توالی اطلاعات ||X||و ردیف هایی از ماتریس مولد را که با ارقام واحد ماتریس مطابقت دارند اضافه کنید ||X||.

توجه کنید که ||KC|| = ||X، DR||،

جایی که ||X||-توالی اطلاعات (از آنجایی که در ماتریس هویت ضرب می شود ||من||),

آ ||DR||- ارقام اضافی بسته به ماتریس ارقام اضافی ||MDR||:

|| DR ||= || X || * || MDR||

7.5 دستور رمزگشایی

در نتیجه انتقال یک کلمه رمز از طریق یک کانال، ممکن است توسط تداخل خراب شود. این باعث می شود کلمه رمز دریافت شده باشد ||PKS||ممکن است با اصل مطابقت نداشته باشد ||KS||.

اعوجاج را می توان با استفاده از فرمول زیر توصیف کرد:

|| PKS || = ||KS || + ||VO ||،

جایی که ||VO||- بردار خطا - ماتریس ردیف با بعد 1* n، با 1 در آن موقعیت هایی که در آن تحریف رخ داده است.

رمزگشایی بر اساس یافتن به اصطلاح سندرم خطای شناسه یا ماتریس ردیف است. ||OP||طول rرتبه ها ( r- تعداد بیت های اضافی یا اضافی در کلمه کد).

شناسه برای یافتن بردار خطای تخمینی استفاده می شود.

شناسه با استفاده از فرمول زیر پیدا می شود:

||OP|| = ||PKS||* ||TPM||،

جایی که ||PKS||-کلمه رمز دریافت شده و احتمالاً خراب شده است.

||TPM||،-ماتریس چک جابجا شده که از ماتریس بیت های اضافی به دست می آید ||MDR||با اختصاص ماتریس هویت به آن در زیر:

مثال ||TPM||:

از آنجا که ||PKS|| = ||KS|| + ||BO||،آخرین فرمول را می توان به صورت زیر نوشت:

||OP|| = ||KS|| * ||TPM||+||VO|| * ||TPM||.

بیایید ترم اول را بررسی کنیم.

||KC||- ماتریس ردیف، با اولین کدسته ها - اطلاعاتی

اجازه دهید اکنون ثابت کنیم که حاصلضرب کلمه رمز است ||KS||بر ||TPM||منجر به یک ماتریس صفر می شود ||0||.

از آنجا که ||KS||- ماتریس ردیف، یک روش ساده برای ضرب ماتریس های مورد بحث در بالا امکان پذیر است.

بنابراین، اولین ترم در

||OP|| = ||KS|| * ||TPM|| + ||VO|| * ||TPM||

همیشه برابر با صفر است و شناسه کاملاً به بردار خطا بستگی دارد ||VO||.

اگر اکنون چنین ماتریس بررسی را انتخاب کنیم TPM، و بنابراین MDRبه طوری که بردارهای خطای مختلف با شناسه های مختلف مطابقت دارند OP،سپس با استفاده از این شناسه ها می توان بردار خطا را یافت که در،و در نتیجه اصلاح این خطاها.

مطابقت شناسه ها با بردارهای خطا از قبل با ضرب بردارهای خطاهای تصحیح شده در پیدا می شود. TPM;

بنابراین، توانایی کد برای تصحیح خطاها به طور کامل توسط ||MDR||.برای ساخت MDRبرای کدهایی که خطاهای یکباره را تصحیح می کنند در هر خط لازم است MDRحداقل 2 واحد داشته باشد. در این مورد نیز لازم است حداقل یک تفاوت بین هر دو خط وجود داشته باشد MDR.

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

ساخت و ساز MDRدر مورد تصحیح چندین خطا کار بسیار دشوارتر می شود. نویسندگان مختلف الگوریتم های ساخت و ساز متفاوتی را یافته اند ||MDR ||برای این مورد، و کدهای مربوطه با نام نویسندگان آنها نامیده می شود.

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

اجازه دهید قوانین رسمی (تولید کننده) را که توسط آنها کدگذاری انجام می شود، تعریف کنیم. تبدیل یک توالی اطلاعات به یک کلمه رمز

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

این روش توصیف کدها برای هر کدی قابل استفاده است، نه فقط برای کدهای خطی. با این حال، در کل بهاندازه جدول کدمعلوم می شود که برای استفاده در عمل بیش از حد بزرگ است.

راه دیگر برای تعیین کدهای بلوک خطی استفاده از به اصطلاح است سیستم های معادلات تولیدی،تعریف قاعده ای که توسط آن کاراکترهای توالی اطلاعات به آن تبدیل می شوند کاراکترهای کد. برای مثال مشابه، سیستم تولید معادلات به شکل زیر خواهد بود:

با این حال، راحت ترین و بصری ترین راه برای توصیف کدهای بلوک خطی، مشخص کردن آنها با استفاده از آن است ماتریس تولید،که شکل فشرده ای از نمایش یک سیستم معادلات تست است.

بلوک خطی(l, /c)-code به طور کامل توسط یک ماتریس G با اندازه تعیین می شود بهایکس پبا عناصر ماتریس باینری در این حالت، هر کد کلمه است ترکیب خطیردیف های ماتریس G و هر ترکیب خطی از ردیف های G یک کلمه رمز است.

ما کدهای بلوک خطی تعریف شده با تولید ماتریس را فراخوانی می کنیم کدهای ماتریسینمایش معمول (متعارف) ماتریس مولد به صورت زیر است:

به عنوان مثال، برای ساده ترین کد (4، 3) با بررسی برابری، ماتریس تولید کننده به صورت زیر خواهد بود:

اجازه دهید تی -(t 1; t 2، ..., tk)بلوک پیامی خواهد بود که باید با استفاده از این کد کدگذاری شود.

سپس کلمه کد مربوطه Uاراده

با در نظر گرفتن ساختار ماتریس جینمادهای کلمه رمز وبه این صورت خواهد بود:

به عبارت دیگر، بهسمت چپ ترین نمادهای کلمه رمز با نمادهای دنباله اطلاعات رمزگذاری شده منطبق است و بقیه (n - به)نمادها ترکیبی خطی از نمادهای توالی اطلاعاتی هستند.

به عنوان مثال، اگر دنباله ورودی رمزگذار t == (10 1)، سپس با استفاده از ماتریس مولد کد به صورت زیر ساخته می شود:

8 فرمانده سه پیشاهنگ را در امتداد جاده اول، سه پیشاهنگ در امتداد جاده دوم، دو نفر در امتداد سوم، و خودش در امتداد جاده چهارم رفت. یک ماتریس تولید کننده برای چنین کدهایی بسازید.

پاسخ:با توجه به طرح کار، پیام دریافت شده توسط فرمانده شخصاً قابل تحریف نیست. بنابراین، ما خود را به مطالعه اطلاعات مخابره شده توسط جنگنده ها محدود می کنیم. در گروهی که در امتداد یکی از جاده‌ها حرکت می‌کنند، هر جنگنده باید یا در مورد کشف یک شی (ما چنین گزارشی را با عنوان "1") یا در مورد عدم وجود یک شی ("0") به فرمانده گزارش دهد. در صورت عدم وجود تحریف، گزارش های هر مبارز از همان گروه باید مطابقت داشته باشد. از این رو:

ماتریس را می توان با شماره گذاری مجدد مبارزان به شکل متعارف درآورد. در امتداد جاده اول ارسال اولین، چهارم و پنجم، در امتداد جاده دوم - دوم، ششم و هفتم، در امتداد جاده سوم - جنگنده های سوم و هشتم. ماتریس مولد زیر را بدست می آوریم:

کد تعریف شده به این صورت نامیده می شود بلوک خطی سیستماتیک(پ،کد cj/ با بررسی های برابری تعمیم یافته.

ماتریس ژنراتورکد خطی به ماتریس اندازه گفته می شود که ردیف های آن بردارهای پایه آن هستند.

مثلا،

ماتریس تولید کد دو کلمه ای (000، 011) است.

برای کد B از مثال 6.3 تولید می کند.

ما می دانیم که کلمات رمز ترکیبی خطی از بردارهای پایه هستند، یعنی. ردیف های ماتریسی به این معنی که کلمات را می توان با ضرب یک بردار با یک ماتریس به دست آورد. بنابراین پیام به صورت برداری نوشته می شود و کلمه کد پیام مربوطه با فرمول محاسبه می شود

بنابراین، بردار بیت ها به دنباله ای از کاراکترهای باینریاز طریق یک کانال منتقل می شود یا در حافظه یک دستگاه ذخیره سازی ضبط می شود.

بیایید به مشکل رمزگشایی بپردازیم.

فرض کنید که برای برخی از بردارهای باینری، همه کدهای کد -code ، ارضای هویت

که در آن نشان دهنده حاصل ضرب اسکالر بردارها و .

در مورد چنین برداری خواهیم گفت که متعامد است. با یافتن چنین بردار، می‌توانیم با استفاده از شناسه (6.2) بررسی کنیم که آیا دنباله دریافتی از کانال یک کلمه رمز است یا خیر.

توجه داشته باشید که (6.2) برای همه رمزها در صورتی معتبر است که برای بردارهای پایه معتبر باشد. اگر

جایی که بالانویس T مخفف transpose است.

هرچه چنین "بررسی" بیشتری پیدا کنیم، ظاهراً می توانیم خطاهای بیشتری را شناسایی و اصلاح کنیم.

تمرین 6.4. ثابت کنید که چک ها یک فضای خطی را تشکیل می دهند.

ما این فضا را فضای متعامد به کد خطی یا می نامیم فضای تست.

تمرین 6.5. بعد را پیدا کنید فضای خطیچک ها

برای تکمیل آخرین تمرین، باید توجه داشته باشید که ماتریس دقیقاً دارای ستون های مستقل خطی است. نه بیشتر (چرا؟) و نه کمتر (چرا؟). بیایید لیستی از شماره های این ستون ها را درست کنیم و این مجموعه اعداد را فراخوانی کنیم مجموعه اطلاعات. کمی بعد معنای این نام روشن تر خواهد شد. اجازه دهید به طور دلخواه مقادیر برداری را در موقعیت هایی که در آن گنجانده نشده اند انتخاب کنیم مجموعه اطلاعات. مقادیر در موقعیت های مجموعه اطلاعات چه مقدار باید باشد تا (6.3) برآورده شود؟ برای پاسخ به این سوال، شما باید یک سیستم معادلات خطی را حل کنید، و سیستم حل کرده است تنها تصمیم.

نتیجه این استدلال ها قضیه است

قضیه.بعد فضای بررسی یک کد خطی برابر است با .

اساس فضای تست را به صورت ماتریس می نویسیم

تماس گرفت بررسی ماتریسکد

ماتریس های بررسی و تولید با رابطه مرتبط هستند

از این رابطه می بینیم که برای هر کلمه رمزی که داریم

این هویت می تواند به عنوان معیاری برای تعلق دنباله دلخواه به یک کد استفاده شود، یعنی. برای تشخیص خطاها

دانستن، می توانید پیدا کنید. به منظور درک نحوه انجام این کار، توجه داشته باشید که یک کد را می توان توسط ماتریس های تولید کننده مختلف مشخص کرد، و اساس فضا را متفاوت انتخاب کرد. علاوه بر این، با جایگزین کردن هر خط با هر ترکیب خطی از این خط با خطوط دیگر، ماتریس مولد جدیدی از همان کد دریافت می کنیم.

مرتب سازی مجدد ستون های یک ماتریس، به طور کلی، منجر به کد متفاوتی می شود، اما این کد متفاوت از نظر ویژگی ها با کد اصلی تفاوتی ندارد. کدهایی که فقط در شماره گذاری موقعیت متفاوت هستند فراخوانی می شوند معادل.

واضح است که برای هر کد یک کد معادل وجود دارد که موقعیت های اول یک مجموعه اطلاعاتی را تشکیل می دهند. ستون های اول یک ماتریس غیر منفرد از اندازه را تشکیل می دهند. با جایگزینی سطرها با ترکیب خطی سطرها (روش گاوسی)، می توان ماتریس حاصل را به شکل کاهش داد.

ماتریس هویت نظم کجاست و مقداری ماتریس اندازه است.

ماتریسی از شکل (6.6) را ماتریس مولد می گویند که به کاهش می یابد فرم سیستماتیک، و کد مربوطه فراخوانی می شود نظام. کدنویسی برای کد سیستماتیک کمی ساده تر از کد است نمای کلی:

, (6.7)

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

برای یک کد سیستماتیک با ماتریس مولد به شکل (6.6)، ماتریس بررسی برابری را می توان با استفاده از فرمول محاسبه کرد.

تمرین 6.6. بررسی (6.7). نکته: برای انجام این کار باید (6.8) و (6.6) را با (6.4) جایگزین کنید.

چطوری پیدا کنم بررسی ماتریسبرای کد غیر سیستماتیک؟

بسیار ساده. لازم است ماتریس را به شکل سیستماتیک درآوریم و از (6.7) استفاده کنیم. اگر اولین ستون‌های ماتریس مولد یک زیرماتریس غیر منفرد را تشکیل دهند (اولین موقعیت‌ها یک مجموعه اطلاعاتی را تشکیل می‌دهند)، سپس برای رساندن آن به شکل سیستماتیک، عملیاتی مانند مرتب کردن مجدد ردیف‌ها و جایگزینی ردیف‌ها با ترکیب خطی ردیف‌ها کافی است. اگر نه، ابتدا باید مجموعه اطلاعات را پیدا کنید و موقعیت ها را مجددا شماره گذاری کنید تا اولین موقعیت ها به اطلاعات تبدیل شوند.

از آنجایی که، طبق تعریف، کد خطی (l, /s) طول است پدر بالا GF(q)یک زیرفضا است GFk(q)فضای برداری GF n(q)،پس باید یک مکمل متعامد از زیرفضا وجود داشته باشد GFk(q)کد خطی (به بخش 1.7.1 مراجعه کنید).

فرض کنید H ماتریسی باشد که سطرهای آن با بردارهای پایه مکمل متعامد یک کد خطی g-ary C با طول مطابقت دارد. پ.سپس برای هر بردار c، متعلق به کد، نمایشگاه:

شرط (2.10) به شخص اجازه می دهد تا عضویت یک دنباله n دلخواه از عناصر را بررسی کند GF(q)یک کد خطی g-ary خاص

اگر یک بردار کد خطی دارای وزن همینگ شو باشد، این بدان معناست که کلمه رمز حاوی نمادهای sho غیر صفر است (طبق تعریف وزن همینگ، به بخش 2.1.4 مراجعه کنید). سپس با توجه به قوانین ضرب ماتریس، حاصل ضرب بردار با مقدار وزن همینگ و ماتریس N tمربوط به ترکیبی خطی از ستون های ماتریس شو است ن.در این مورد، تساوی (2.10) به وضوح برقرار است اگر و فقط اگر هیچ ستونی از ماتریس وجود نداشته باشد. نوابسته خطی

بنابراین شرط وجود چند کد خطی یک کلمه رمز با وزن همینگ شو در مجموعه کلمات رمز وجود در ماتریس است. نستون های خطی وابسته به تعداد شو. همچنین از این نتیجه می شود که یک کد خطی دارای حداقل وزن (به بخش فرعی 2.1.4 مراجعه کنید) حداقل مقداری ω دارد اگر و فقط اگر هر یک از ω - 1 ستون های ماتریس H مستقل خطی باشند. بنابراین، با توجه به نابرابری (2.6)، به منظور یافتن یک کد خطی با حداقل وزن شو، تصحیح تیخطاها، فقط ماتریس را پیدا کنید N،که کمتر از شو - 1 = 2 ندارد -tهر ستون به صورت خطی مستقل بود.

بیایید نگاهی دقیق تر به ماتریس بیندازیم ن.همانطور که در بالا ذکر شد، توسط ردیف های ماتریس نبردارهای پایه متمم متعامد کد خطی هستند. اگر مجموعه n دنباله ها یک زیر فضای بعد را تشکیل دهند به،سپس متمم متعامد این زیرفضا دارای بعد خواهد بود کامپیوتر(به زیر پاراگراف های 1.7.1 و 1.7.2 مراجعه کنید). ابعاد فرعی پ- بهبرای بسیاری از کامپیوتربردارهای پایه بنابراین ماتریس نباید شامل کامپیوترردیف های مستقل خطی

از آنجایی که ماتریس های G و نمتعلق به همان فضای n-دنباله، سپس تعداد ستون های ماتریس است نبرابر است با تعداد ستون های ماتریس G. بنابراین، ماتریس ندارای اندازه (l - به) x l. تمام ستون های ماتریس N،همانطور که قبلا ذکر شد، آنها به صورت خطی تشکیل می شوند گروه های مستقلتوسط 2 تنستون ها.

مطابق رابطه (2.2)، هر کلمه رمزی از یک کد خطی، ترکیبی خطی از ردیف‌های ماتریس مولد G کد است. در این مورد، بدیهی است که هر سطر از ماتریس G مربوط به کلمه رمز خاصی است. بنابراین، رابطه (2.10) را می توان به صورت زیر بازنویسی کرد:

حاصل حاصل ضرب ماتریس های اندازه G به*چه N tسایز l x (کامپیوتر)ماتریس اندازه است به x (l - به)،متشکل از عناصر صفر

ماتریس ناندازه ( p-k)x l که سطرهای آن بردارهای پایه متمم متعامد زیرفضای کد خطی هستند، نامیده می شود. بررسی ماتریسکد خطی

با توجه به رابطه (2.4)، ماتریس مولد یک کد خطی سیستماتیک از یک ماتریس واحد نظم تشکیل شده است. بهو ماتریس نمادهای بررسی اندازه به x (l - به)،که به نوبه خود، بسط ماتریس هویت است. همانطور که در پیوست 1 نشان داده شده است، ضرب دو ماتریس را می توان با تقسیم ماتریس های ضرب به ماتریس انجام داد. سایز کوچکتر(بلوک ها) با ضرب بعدی بلوک های منفرد ماتریس های ضرب شده. سپس برای ماتریس های G و نمی توان نوشت:

تعداد ستون ها در بلوک ها الف و بماتریس ها ن 7 باید با تعداد خطوط بلوک مطابقت داشته باشد اکو آرماتریس های G (طبق قوانین ضرب ماتریس). ماتریس حاصل باید دارای اندازه /s * (l - به).بدیهی است که اگر قرار دهیم آ = -رو که در= El_/s، سپس ماتریس نمعادله (2.11) را برآورده خواهد کرد.

بنابراین ماتریس N tتوسعه ماتریس است -رو علاوه بر ماتریس - آرماتریس نشامل ماتریس هویت نظم است پ - به.ماتریس N tنتیجه جابجایی ماتریس است ن.

نتیجه انتقال مجدد یک ماتریس، ماتریس اصلی است. بنابراین ماتریس نرا می توان با جابجایی ماتریس به دست آورد N t.از آنجایی که برای هر عنصر یک فیلد GF[ 2) a = - a درست است، سپس برای یک کد خطی باینری درست است R--R.

ماتریس نکد خطی باینری به شکل زیر خواهد بود:

ماتریس R،موجود در ماتریس G و حاوی نمادهای چک، با جابجایی ماتریس به دست می آید R t،در ماتریس گنجانده شده است ن.

بنابراین، ساخت یک کد خطی به جستجوی ماتریس کاهش می یابد ن.با توجه به یک ماتریس داده شده نیافتن ماتریس G آسان است.

مثال 2.1.4. اجازه دهید ساخت یک کد خطی باینری را در نظر بگیریم - یک کد روی GF(2) که یک خطای کلمه رمز را با یک توالی اطلاعات اندازه تصحیح می کند. به= 3 بیت

با توجه به رابطه (2.9)، برای یک کد با حداکثر فاصله r = 2-t == 2. سپس l = /c + r = 3 + 2 = 5. با این حال، همانطور که در بخش فرعی بعدی نشان داده خواهد شد، یک کد باینری خطی (5،3) قادر به تصحیح یک خطای کلمه کد واحد نیست. در این حالت حداقل تعداد کاراکترهای اضافی برای این مورد است جی= 3، و کد مورد نظر یک کد خطی باینری (6،3) است.

بنابراین، در در این موردماتریس نشامل یک ماتریس بررسی با اندازه /сх(l-/с) = 3*3 و یک ماتریس هویتی با ترتیب p-k= 3.

تمام ستون های ماتریس نباید گروه های مستقل خطی از دو ستون و یک گروه وابسته خطی از سه ستون تشکیل دهند. این شرط، برای مثال، توسط دنباله های 101، 110 و 011 بر روی GF(2) برآورده می شود. دنباله های مشخص شده ستون های ماتریس را تشکیل می دهند R t،در ماتریس گنجانده شده است ن.سایر عناصر ماتریس نمطابق با ماتریس هویت مرتبه 3:

با اضافه کردن به ماتریس هویت مرتبه 3، ماتریس P با جابجایی ماتریس به دست می آید. R t،ماتریس G را دریافت می کنیم:

اجازه دهید روند تشکیل و ساختار کلمه کد یک کد خطی باینری (6، 3) را با یک ماتریس مولد به شکل (2.12) در نظر بگیریم:

سه نماد اول کلمه رمز (ci - Сз) حاوی نمادهای اطلاعاتی (/ 1 - r "з) هستند که در نتیجه ضرب ماتریس دنباله اطلاعات تشکیل شده اند. منبه ماتریس هویت مرتبه 3، که بخشی از ماتریس G است. نمادهای باقی مانده از کلمه رمز (C4 - Cb) حاوی نمادهای چک هستند. (t^ - tz)،در نتیجه ضرب ماتریس توالی اطلاعات در ماتریس نماد چک به دست می آید R،همچنین در ماتریس G گنجانده شده است.

به راحتی می توان بررسی کرد که در مورد کد (6، 3) از مثال 2.1.4، حداقل تعداد نمادهای غیر صفر در بین همه رمزها سه باشد (کلمات کد 001101، 010011، 100110 و 111000). بدین ترتیب، د*= 3 و طبق رابطه (2.5) کد باید یک خطای کلمه رمز را تصحیح کند. همانطور که در زیر پاراگراف بعدی نشان داده خواهد شد، این در واقع مورد است.