کدگذاری خطی شبکه

در شبکه های مخابراتی، کدگذاری خطی شبکه، یا ساده تر، کدگذاری شبکه، یا کدینگ شبکه، روشی برای انتقال داده هاست که در آن گره های میانی شبکه، داده ها را با بهره گیری از ترکیب های خطی آنها، از گره های مبدأ به گره های مقصد منتقل می کنند.
کدگذاری خطی شبکه، برای بهبود گذرداد، کارایی و مقیاس پذیری شبکه، یا برای امنیت انتقال داده ها با جلوگیری از شنود به کار می رود. گره های شبکه چندین بستۀ داده ( data packets ) را از مبدأ ( و گره های پیشین ) گرفته و آنها را برای رساندن به مقصد، ترکیب خطی می کنند. این فرآیند، بیشتر برای دستیابی به حداکثر نرخ انتقال اطلاعات ممکن در شبکه استفاده می شود.
از دیدگاه تئوری، ثابت شده است که کدگذاری خطی برای دستیابی به کران بالایی نرخ انتقال داده ها در شبکه ای با یک مبدأ ( منبع داده ها ) و چند مقصد، کافی است. [ ۱] بااین حال، کدگذاری خطی به طور کلی برای هر شبکه ای کافی نیست؛ حتی با بهره گیری از نسخه های عمومی تر خطی بودن، مانند کدگذاری کانولوشنال و کدگذاری بانک فیلتر. [ ۲] یافتن کدگذاری بهینه برای شبکه ها و با هر نیاز دلخواه، یک مسئله دشوار است که می تواند اِن پی سخت[ ۳] و حتی غیرقابل تصمیم گیری باشد. [ ۴] [ ۵]
در مسئله کدگذاری خطی شبکه، گروهی از گره ها ( P ) ، بسته های داده را از گره های مبدأ ( S ) به گره های مقصد ( K ) منتقل می کنند. هر گره، بسته های جدیدی تولید می کند که ترکیبی خطی از بسته های دریافت شدۀ آن هستند. ضرایب این ترکیب خطی، از یک میدان متناهی - معمولاً G F ( 2 s ) - هستند، که s، طول بسته بر حسب بیت است.
هر گرۀ p k با I n D e g ( p k ) = S ، پیام ( بستۀ داده ) X k را تولید می کند که ترکیب خطی پیام های دریافت شده { M i } i = 1 S است:
که g k i ها، ضرایبی هستند که از G F ( 2 s ) انتخاب شده اند. ازآنجاکه این محاسبات در یک میدان متناهی انجام می شود، طول پیام تولیدشده و پیام های اصلی برابر است. هر گره، X k محاسبه شدۀ را به همراه ضرایب g k i که در مرحله k th استفاده شده اند به گره های بعدی گسیل می کند.
گره های مقصد، این پیام های کدِشبکه شده را دریافت کرده، آنها را در یک ماتریس، گرد می آورند. پیام های ( بسته های ) اصلی را می توان با حذف گاوسی این ماتریس، بازیافت. [ ۶] اگر این ماتریس به شکل سطری پلکانی در آید، پیام های کدگشایی شده، همان ردیف های ماتریس، e i = ، خواهند بود.