کد خطی

توسط علی رضا نقش نیلچی | دوشنبه سیزدهم اردیبهشت ۱۴۰۰ | 0:36

از ویکیپدیا، دانشنامه آزاد

در نظریه کدگذاری ، یک کد خطی یک IS کد تصحیح خطا که هر ترکیب خطی از کلمه های کد همچنین یک کلمه کد. کدهای خطی به طور سنتی به کدهای بلوک و کدهای کانولوشن تقسیم می شوند ، اگرچه کدهای توربو را می توان ترکیبی از این دو نوع دانست. [1] کدهای خطی امکان الگوریتم های رمزگذاری و رمزگشایی کارآمدتر از سایر کدها را دارند (رجوع کنید به رمزگشایی سندرم ). [ نیاز به منبع ]

کدهای خطی در تصحیح خطای رو به جلو استفاده می شوند و در روش های انتقال نمادها (به عنوان مثال ، بیت ها ) در یک کانال ارتباطی اعمال می شوند تا در صورت بروز خطا در ارتباط ، برخی از خطاها توسط گیرنده بلوک پیام اصلاح یا شناسایی شوند. کلمات رمز در یک کد بلوک خطی بلوک هایی از نمادها هستند که با استفاده از نمادهای بیشتر از مقدار اصلی ارسال شده کدگذاری می شوند. [2] یک کد خطی با طول n بلوک های حاوی n نماد را انتقال می دهد . به عنوان مثال ، کد [7،4،3] Hamming یک کد باینری خطی استکه نمایانگر پیامهای 4 بیتی با استفاده از کلمات رمز 7 بیتی است. دو کلمه کد مشخص حداقل در سه بیت متفاوت است. به عنوان یک نتیجه ، حداکثر دو خطا در هر رمز ورود قابل شناسایی است در حالی که یک خطای تنها قابل اصلاح است. [3] این کد شامل 2 کلمه رمز 4 = 16 است.

فهرست

تعریف و پارامترها [ ویرایش ]

یک کد خطی با طول n و رتبه k یک زیر فضای فضایی خطی C با بعد k از فضای بردار است $\ mathbb {F} _ {q} ^ {n}$ جایی که $\ mathbb {F} _ {q}$ است زمینه محدود با Q عناصر. به چنین کدی کد q -ary گفته می شود. اگر q = 2 یا q = 3 باشد ، کد به ترتیب یک کد باینری یا یک کد سه گانه توصیف می شود. بردارهای موجود در C را رمزعبور می نامند . اندازه از یک کد تعداد کلمه های کد است و معادل Q K .

وزن یک کلمه کد تعداد عناصر غیر صفر آن که هستند و است فاصله بین دو کلمه های کد است فاصله همینگ بین آنها، این است که، تعدادی از عناصر که در آن متفاوت است. فاصله d کد خطی حداقل وزن کلمات رمز غیر صفر آن است ، یا معادل آن ، حداقل فاصله بین کدهای رمزگذاری مجزا است. یک کد خطی به طول N ، بعد ک ، و فاصله د یک [به نام N ، K ، D ] کد.

ما می خواهیم بدهیم $\ mathbb {F} _ {q} ^ {n}$ مبنای استاندارد زیرا هر مختصات نشان دهنده "بیتی" است که از طریق "کانال پر سر و صدا" با احتمال کمی خطای انتقال ( کانال متقارن باینری ) منتقل می شود. اگر از مبنای دیگری استفاده شود ، این مدل قابل استفاده نیست و معیار Hamming همانطور که می خواهیم تعداد خطاهای انتقال را اندازه گیری نمی کند.

ماتریس های تولید کننده و بررسی [ ویرایش ]

به عنوان یک فضای فرعی خطی از $\ mathbb {F} _ {q} ^ {n}$ ، کل کد C (که ممکن است بسیار بزرگ باشد) ممکن است به عنوان دهانه یک مجموعه نشان داده شود $ک$ کلمات رمز (که در جبر خطی به عنوان مبنایی شناخته می شود ). این کلمات رمز اساسی اغلب در ردیف های ماتریس G جمع می شوند که به عنوان ماتریس تولید کننده کد C شناخته می شوند . وقتی G فرم ماتریس بلوک را دارد ${\ displaystyle {\ boldsymbol {G}} = [I_ {k} | P]}$ ، جایی که $من_ {k}$ را نشان می دهد $k \ بار k$ ماتریس هویت و P برخی است $k \ times (nk)$ ماتریس ، سپس می گوییم G به شکل استاندارد است .

ماتریس H نشان دهنده یک تابع خطی است $\ phi: \ mathbb {F} _ {q} ^ {n} \ به \ mathbb {F} _ {q} ^ {nk}$ که هسته است C است که به نام ماتریس چک از C (یا گاهی اوقات یک ماتریس بررسی همزادی). معادل آن ، H ماتریسی است که فضای نول آن C است . اگر C یک کد با ماتریس تولید کننده G به شکل استاندارد است ، ${\ displaystyle {\ boldsymbol {G}} = [I_ {k} | P]}$ ، سپس ${\ displaystyle {\ boldsymbol {H}} = [- P ^ {T} | I_ {nk}]}$ یک ماتریس بررسی برای C. کد تولید شده توسط H کد دوگانه C نامیده می شود. می توان تأیید کرد که G یک است $k \ times n$ ماتریس ، در حالی که H یک است ${\ displaystyle (nk) \ بار n}$ ماتریس

خطی بودن تضمین می کند که حداقل فاصله Hamming d بین یک رمز رمز c 0 و هر یک از دیگر رمزهای رمز c ≠ c 0 مستقل از c 0 است . این از ویژگی بدست می آید که تفاوت c - c 0 از دو کلید رمز در C نیز یک رمز کد است (به عنوان مثال ، عنصری از فضای فضایی C ) ، و ویژگی که d ( c ، c 0 ) = d ( c - c 0 است) ، 0). این ویژگی ها حاکی از آن است

${\ displaystyle \ min _ {c \ in C، \ c \ neq c_ {0}} d (c، c_ {0}) = \ min _ {c \ in C، \ c \ neq c_ {0}} d (c-c_ {0}، 0) = \ min _ {c \ in C، \ c \ neq 0} d (c، 0) = d.}$

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

فاصله د از یک کد خطی C نیز برابر با حداقل تعداد ستون خطی وابسته از ماتریس چک H .

اثبات: چون ${\ boldsymbol {H}} \ cdot {\ boldsymbol {c}} ^ {T} = {\ boldsymbol {0}}$ ، که معادل آن است $\ sum _ {i = 1} ^ {n} (c_ {i} \ cdot {\ boldsymbol {H_ {i}}}) = {\ boldsymbol {0}}$ ، جایی که ${\ boldsymbol {H_ {i}}}$ هست $من ^ {th}$ ستون از ${\ boldsymbol {H}}$ . آن موارد را با حذف کنید{\ displaystyle c_ {i} = 0} $c_ {i} = 0$ ، آنهایی که ${\ boldsymbol {H_ {i}}}$ با $c_ {i} \ neq 0$ وابسته خطی هستند. از این رو، $د$ حداقل حداقل ستون های وابسته خطی است. از طرف دیگر ، حداقل ستون های وابسته خطی را در نظر بگیرید $\ {{\ boldsymbol {H_ {j}}} | j \ در S \}$ جایی که $S$ مجموعه شاخص ستون است. $\ sum _ {i = 1} ^ {n} (c_ {i} \ cdot {\ boldsymbol {H_ {i}}}) = \ sum _ {j \ in S} (c_ {j} \ cdot {\ boldsymbol {H_ {j}}}) + \ sum _ {j \ notin S} (c_ {j} \ cdot {\ boldsymbol {H_ {j}}}) = {\ boldsymbol {0}}$ . اکنون بردار را در نظر بگیرید ${\ boldsymbol {c '}}$ به طوری که $c_ {j} ^ {'} = 0$ اگر $j \ notin S$ . توجه داشته باشید ${\ boldsymbol {c '}} \ در C$ زیرا ${\ boldsymbol {H}} \ cdot {\ boldsymbol {c '}} ^ {T} = {\ boldsymbol {0}}$ . بنابراین ، ما داریم $d \ leq wt ({\ boldsymbol {c '}})$ ، که حداقل تعداد ستون های وابسته خطی در است ${\ boldsymbol {H}}$ . بنابراین ملک مورد ادعا اثبات شده است.

مثال: کدهای همینگ [ ویرایش ]

مقاله اصلی: کد همینگ

به عنوان اولین کلاس کدهای خطی که برای تصحیح خطا تولید شده اند ، کدهای Hamming به طور گسترده ای در سیستم های ارتباطی دیجیتال استفاده شده اند. برای هر عدد صحیح مثبت $r \ geq 2$ ، وجود دارد $[2 ^ {r} -1،2 ^ {r} -r-1،3] _ {2}$ کد همینگ از آنجا که $d = 3$ ، این کد Hamming می تواند خطای 1 بیتی را اصلاح کند.

مثال: کد بلوک خطی با ماتریس مولد زیر و ماتریس بررسی برابری یک است $[7،4،3] _ {2}$ کد همینگ

${\ boldsymbol {G}} = {\ start {pmatrix} 1 \ 0 \ 0 \ 0 \ 1 \ 1 \ 0 \\ 0 \ 1 \ 0 \ 0 \ 0 \ 1 \ 1 \\ 0 \ 0 \ 1 \ 0 \ 1 \ 1 \ 1 \\ 0 \ 0 \ 0 \ 1 \ 1 \ 0 \ 1 \ end {pmatrix}} ،$ ${\ boldsymbol {H}} = {\ start {pmatrix} 1 \ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \\ 1 \ 1 \ 1 \ 0 \ 0 \ 1 \ 0 \\ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \ 1 \ end {pmatrix}}$

مثال: کدهای هادامارد [ ویرایش ]

مقاله اصلی: کد هادامرد

کد هادامارد یک است $[2 ^ {r} ، r ، 2 ^ {r-1}] _ {2}$ کد خطی و قادر به اصلاح بسیاری از خطاها است. کد هادامارد را می توان ستون به ستون ساخت: $من ^ {th}$ ستون بیت های نمایش دودویی عدد صحیح است $من$ ، همانطور که در مثال زیر نشان داده شده است. کد هادامارد حداقل فاصله دارد $2 ^ {r-1}$ و بنابراین می تواند اصلاح کند $2 ^ {{r-2}} - 1$ خطاها

مثال: کد بلوک خطی با ماتریس ژنراتور زیر یک است $[8،3،4] _ {2}$ کد هادامارد: ${\ boldsymbol {G}} _ {Had} = {\ start {pmatrix} 0 \ 0 \ 0 \ 0 \ 1 \ 1 \ 1 \ 1 \\ 0 \ 0 \ 1 \ 1 \ 0 \ 0 \ 1 \ 1 \\ 0 \ 1 \ 0 \ 1 \ 0 \ 1 \ 0 \ 1 \ end {pmatrix}}$ .

کد Hadamard یک مورد خاص از کد Reed – Muller است . اگر ستون اول (ستون تمام صفر) را از خارج کنیم ${\ boldsymbol {G}} _ {Had}$ ، ما گرفتیم $[7،3،4] _ {2}$ کد simplex ، که کد دوگانه کد Hamming است.

الگوریتم نزدیکترین همسایه [ ویرایش ]

پارامتر d با توانایی تصحیح خطا کد ارتباط نزدیک دارد. ساختار / الگوریتم زیر این را نشان می دهد (الگوریتم رمزگشایی نزدیکترین همسایه):

ورودی: بردار دریافت شده v در $\ mathbb {F} _ {q} ^ {n}$ .

خروجی: یک رمز رمز $w$ که در $ج$ نزدیکترین به $v$ در صورت وجود

شروع با $t = 0$ ، دو مرحله زیر را تکرار کنید.
عناصر توپ شعاع (Hamming) را برشمارید $تی$ در اطراف کلمه دریافت شده $v$ ، مشخص شده ${\ displaystyle B_ {t} (v)}$ .
- برای هر $w$ که در ${\ displaystyle B_ {t} (v)}$ ، بررسی کن اگر $w$ که در $ج$ . اگر چنین است ، برگردید $w$ به عنوان راه حل
افزایش $تی$ . فقط وقتی شکست بخورید ${\ displaystyle t> (d-1) / 2}$ بنابراین شمارش کامل است و هیچ راه حلی پیدا نشده است.

ما می گوییم که یک خطی است $ج$ است $تی$ تصحیح خطا اگر حداکثر یک کلمه رمز در آن وجود داشته باشد ${\ displaystyle B_ {t} (v)}$ ، برای هر $v$ که در $\ mathbb {F} _ {q} ^ {n}$ .

علامت گذاری رایج [ ویرایش ]

مقاله اصلی: کد بلوک § علامت گذاری معروف

کدها به طور کلی اغلب با حرف C نشان داده می شوند ، و یک کد از طول n و از درجه k (به عنوان مثال ، داشتن کلمات کد k در اساس آن و k ردیف در ماتریس تولید آن ) به طور کلی به عنوان ( n ، k ) شناخته می شود کد کدهای بلوک خطی غالباً به عنوان کدهای [ n ، k ، d ] نشان داده می شوند ، جایی که d به حداقل فاصله هامینگ کد بین هر دو کلمه کد اشاره دارد.

( علامت [ n ، k ، d ] را نباید با علامت ( n ، M ، d ) که برای نشان دادن کد غیر خطی طول n ، اندازه M (یعنی داشتن کلمات کد M ) و حداقل Hamming اشتباه گرفته می شود فاصله د .)

سینگلتون مقید [ ویرایش ]

Lemma ( Singleton binded ): هر کد خطی [n ، k ، d] C را برآورده می کند $k + d \ leq n + 1$ .

کد C که پارامترهای آن k + d = n + 1 را برآورده می کند ، حداکثر فاصله قابل تفکیک یا MDS نامیده می شود . چنین کدهایی ، هنگامی که وجود داشته باشند ، به تعبیری بهترین حالت ممکن را دارند.

اگر C 1 و C 2 دو کد طول n باشند و اگر در گروه متقارن S n جایگزینی p وجود داشته باشد (c 1 ، ...، c n ) در C 1 اگر و فقط اگر (c p (1 ) ، ...، ج ص (N) ) در C 2 ، پس ما می گویند C 1 و C 2 هستند معادل جایگشت . به طور کلی ، اگر وجود دارد $n \ n بار$ ماتریس تک صدایی $M \ colon \ mathbb {F} _ {q} ^ {n} \ به \ mathbb {F} _ {q} ^ {n}$ که C 1 را به صورت غیر شکل به C 2 می فرستد ، سپس می گوییم C 1 و C 2 معادل هستند .

Lemma : هر کد خطی جایگزین معادل کدی است که به صورت استاندارد است.

قضیه بونیسولی [ ویرایش ]

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

مثالها [ ویرایش ]

برخی از نمونه های کد خطی عبارتند از:

کدهای تکراری
کدهای برابری
کدهای حلقوی
کدهای همینگ
کد Golay ، هم نسخه باینری و هم نسخه سه تایی
کدهای چند جمله ای که کد BCH نمونه ای از آنهاست
کدهای Reed – Solomon
کدهای Reed – Muller
کدهای Goppa
کدهای بررسی برابری با تراکم کم
کدهای گسترش دهنده
کدهای بررسی برابری چند بعدی
کدهای Toric
کدهای توربو

تعمیم [ ویرایش ]

فضاهای هم زدن بیش از حروف غیر میدان نیز در نظر گرفته شده است ، به ویژه بیش از حلقه های محدود (به ویژه بیش از Z 4 ) که باعث ایجاد ماژول ها به جای فضاهای برداری و کدهای حلقه ای خطی (مشخص شده با زیر مدول ها ) به جای کدهای خطی می شوند. معیار متداول مورد استفاده در این مورد فاصله لی . یک فاصله سنجی خاکستری وجود دارد $\ mathbb {Z} _ {2} ^ {2m}$ (یعنی GF (2 متر )) با فاصله Hamming و $\ mathbb {Z} _ {4} ^ {m}$ (همچنین با GR (4 ، متر) نشان داده می شود) با فاصله لی. جذابیت اصلی آن این است که بین برخی از کدهای "خوب" که خطی نیستند ، مکاتبه ای برقرار می کند $\ mathbb {Z} _ {2} ^ {2m}$ به عنوان تصاویر کدهای حلقه ای خطی از $\ mathbb {Z} _ {4} ^ {m}$ . [6] [7] [8]

اخیراً ، [ چه زمانی؟ ] برخی از نویسندگان چنین کدهایی را بیش از حلقه ها به عنوان کدهای خطی نیز ذکر کرده اند. [9]

همچنین به [ ویرایش ] مراجعه کنید

روش های رمزگشایی

https://en.wikipedia.org/wiki/Linear_code

مشخصات وب

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

ریاضیات

آموزش ریاضی