۱

۱

۰

یک سیستم با بهره گرفتن از یای مجزا یا ( و{F وT} ) یک گروه آبلی است. ترکیب
عملگر­های Λ و روی مولفه­های {F وT} میدان را تولید می­ کند. اگر سه داده ورودی داشته باشیم، نتیجه هنگامی درست است که دقیقا یکی ازاین داده ­ها درست باشد. اگر تعداد زیادی داده ورودی داشته باشیم، نتیجه هنگامی درست است که تعداد فرد از داده ­ها درست باشد.
۲-۲- کد­گذاری شبکه^[۶۱]
امروزه شبکه ­های ارتباطی در اساس عمل مشترک هستند، خواه بسته­ها در اینترنت یا سیگنال­ها در شبکه ­های تلفنی باشند، اطلاعات مانند عبور اتومبیل­ها در بزرگراه یا انتقال جریان در لوله­ها انتقال می­یابند. یعنی جریان داده ­های مستقل ممکن است در منابع اشتراک داشته باشند، اما اطلاعات خودشان مجزا باشد. مسیر­یابی، ذخیره سازی داده ­ها و به طور کلی تمام اعمال شبکه بر فرض ارسال ساده اطلاعات استوار است. کد­گذاری شبکه حیطه جدیدی است که این فرض را می­شکند و به جای ارسال ساده اطلاعات، گره­ها می­توانند چند بسته ورودی را با هم ترکیب کنند و به صورت یک یا چند بسته خروجی درآورند. مثالی ساده در زمینه
شبکه ­های بی­سیم ساختاری با سه گره است که در شکل ۲-۱ نشان داده شده است.کد­گذاری خطی شبکه در حالت کلی مشابه این مثال است با این تفاوت که در آن عمل جای خود را به ترکیبات خطی می­دهد.

شکل ۲-۱مثالی ساده از کد­گذاری شبکه.
گره های و می­خواهند بسته­ها را از طریق گره میانی رد و بدل کنند. گره بسته و گره بسته را می­فرستد و در ادامه به جای و توزیع می­گردد و و می­توانند بسته­های مورد نظر خود را احیا کنند و در این حالت تعداد انتقالات کاهش می­یابد.
کد­گذاری شبکه در حیطه­هایی که تنها اطلاعات جزیی و یا غیر قطعی برای تصمیم گیری در دسترس است، بسیار مناسب می­باشد. دریافت موفقیت­آمیز اطلاعات، به دریافت حجم مشخصی از بسته­ها وابسته نیست بلکه به دریافت تعداد کافی از بسته­های مستقل وابسته است[۴].

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

۲-۲-۱- کد­گذاری خطی شبکه ^[۶۲]
سیستمی را در نظر بگیرید که مانند یک مسیریاب یا یک گره در یک شبکه توزیع نظیر به نظیر به ارسال اطلاعات می ­پردازد. در روش­های سنتی هنگامی که بسته­های اطلاعاتی به تعدادی از گره­ها می­رسیدند، آن گره­ها نیز به آسانی همین کار را تکرار می­کردند. با بهره گرفتن از کد­گذاری شبکه، به گره این اجازه را می­دهیم که تعدادی از بسته­هایی که دریافت کرده است را با هم ترکیب کند و به یک یا چند بسته خروجی تبدیل نماید. فرض کنید که هر بسته شامل بیت باشد. هنگامی که بسته­هایی که می­خواهند با هم ترکیب شوند دارای اندازه یکسان نباشند، بسته­هایی با اندازه کمتر با دنباله­ای از صفرها افزوده می­شوند. می­توانیم بیت متوالی از یک بسته را به صورت نمادی روی میدان معرفی کنیم و هر بسته شامل یک بردار با مولفه می­باشد. با استفاده ازکد­گذاری خطی شبکه، بسته­های خارج شده ترکیب خطی از بسته­های اصلی هستند، جایی­که جمع و ضرب روی میدان انجام می­ شود. دلیل انتخاب چارچوب خطی این است که الگوریتم­ها برای کد­گذاری^[۶۳] و از کد خارج کردن^[۶۴] بسیار قابل فهم هستند.
ترکیبات خطی سلسله­وار نیستند، اگر ما بسته­هایی به طول را با هم ترکیب کنیم، بسته کد­گذاری بدست آمده دارای طول است. یک بسته کد­گذاری شده عموما شامل اطلاعاتی در مورد چندین بسته اصلی است[۴].
۲-۲-۲- کد­گذاری
فرض کنید که تعدادی بسته اصلی ، توسط یک یا چند منبع تولید شده ­اند. در کد­گذاری خطی شبکه هر بسته در شبکه به دنباله­ای از ضرایب در مرتبط است و ، این مجموع برای هر مولفه استفاده می­ شود، یعنی جاییکه و به ترتیب امین مولفه هستند. به منظور ساده سازی فرض می­کنیم که هر بسته شامل ضرایب که بردار کد­گذاری نامیده می­ شود و داده کد­گذاری شده که بردار اطلاعات نامیده می­ شود، است. بردارهای کد­گذاری به منظور از کد خارج کردن داده ­ها توسط گیرنده­ها استفاده می­ شود. به عنوان مثال، بردار کد­گذاری ، جایی­که ۱ مولفه ام است، به این معناست که بردار اطلاعات برابر است. کدگذاری می ­تواند به صورت بازگشتی انجام گیرد. گره­ای را در نظر بگیرید که مجموعه از بسته­های کد­گذاری شده را دریافت و ذخیره کرده است. جایی­که بردار کد­گذاری امین بسته و بردار اطلاعات امین بسته است. این گره می ­تواند بسته کد­گذاری شده جدید را با انتخاب یک مجموعه از ضرایب را تولید و ترکیب خطی را محاسبه نماید[۴].
۲-۲-۳- از کد درآوردن
فرض کنید که یک گره مجموعه را دریافت کرده است. به منظور بازیابی بسته­های اصلی لازم است که دستگاه را حل کنیم. (جایی­که ها مجهول هستند.) این دستگاه خطی دارای معادله و مجهول است. به منظور داشتن شانس احیای تمام داده ­ها باید داشته باشیم ، یعنی تعداد بسته­های دریافت شده باید حداقل به بزرگی اندازه بسته­های اصلی باشد. برعکس شرط شرط کافی نیست، چون برخی از ترکیب­ها باید مستقل خطی باشند[۴].
۲-۲-۴- چگونه ترکیبات خطی را انتخاب کنیم؟
مساله کد­گذاری شبکه این است که هر گره شبکه چه ترکیب خطی را انجام دهد. یک الگوریتم ساده این است که هر گره در شبکه به طور یکنواخت و به صورت تصادفی ضرایب را روی میدان به روشی کاملا مستقل و غیر متمرکز، انتخاب کند. با کد­گذاری تصادفی شبکه، احتمالات قطعی از انتخاب ترکیبات مستقل خطی موجود است. این احتمالات به اندازه میدان مربوط است. نتایج شبیه­­ سازی شده حاکی از آن است که برای میدان­هایی با اندازه کوچک (مثلا ) احتمالات ناچیز و اندک است. الگوریتم­هایی نیز موجودند که می­توان با بهره گرفتن از آن­ها کد­های شبکه را طراحی کرد. این الگوریتم­ها مشخص می­ کنند که هر گره در شبکه چه ترکیبات خطی را روی بسته­ها پیاده کند و از آن­جایی که هر گره از ضرایب خطی ثابتی استفاده می­ کند، لازم است که بسته­ها تنها بردار اطلاعات را با خود حمل کنند [۴].
۲-۲-۵- ملاحظات عملی
در این بخش ابتدا به مبحث از کد خارج کردن اشاره می­کنیم. از کد درآوردن نیازمند حل یک مجموعه از معادلات خطی است که در عمل به صورت زیر انجام می­ شود.
یک گره بردارهای کد­گذاری را که دریافت کرده است، همانند بسته­های اصلی خودش، سطر به سطر در ماتریسی که به آن ماتریس از کد درآوردن گویند، ذخیره می­ کند، که در ابتدا تنها شامل بسته­های غیر کد­گذاری شده است که توسط این گره به همراه بردارهای کد­گذاری مورد نظر منتشر می­ شود. هنگامی که یک بسته کد­گذاری شده دریافت می­ شود به عنوان سطر آخر وارد ماتریس از کد خارج کردن می­ شود. ماتریس ضرایب با بهره گرفتن از روش حذفی گاوس به یک ماتریس مثلثی تبدیل می­گردد. بسته دریافت شده را تغییر­یافته نامند اگر رتبه ماتریس را افزایش دهد. اگر یک بسته تغییر­یافته نباشد به سطری از صفرها توسط روش حذفی گاوس کاهش می­یابد. به محض اینکه ماتریس شامل یک سطر به شکل باشد، گره می­داند که بسته اصلی برابراست. این حالت هنگامی رخ می­دهد که بردار کد­گذاری مستقل خطی دریافت شود. توجه کنید که لازم نیست از کد خارج کردن برای تمام گره­ها انجام شود، تنها گره­های گیرنده این عمل را انجام می­ دهند[۴].
دوره­ها^[۶۵]