در تئوری کدگذاری کانال مخابراتی، کدهای هم پیوسته ( Concatenated codes ) ، دسته ای از کدهای تصحیح کننده خطا هستند که از به هم پیوستن یک کد درونی ( inner code ) و یک کد بیرونی ( outer code ) به دست می آیند. این کدها را دیو فورنی در سال 1966، در جست وجوی کدی که هم احتمال خطای آن با افزایش طول کد، به طور نمایی ( Exponential ) کاهش یابد و هم دارای پیچیدگیِ کدگشاییِ چندجمله ای برحسب طول کد ( Polynomial - time ) باشد، پیش نهاد. [ ۱] کدهای هم پیوسته در دهۀ هفتاد میلادی در مخابرات فضایی، استفاده شد.
کدگذاری کانال، به فرستادن رشته ای از داده ها - با بیشترین نرخ ( سرعت ) ممکن - روی یک کانال مخابراتی مشخص، و سپس کدگشایی قابل اطمینان داده ها در گیرنده و به کمک الگوریتم های قابل پیاده سازیِ کدگذاری و کدگشایی می پردازد.
قضیه کدگذاری کانال شانون نشان می دهد که برای بسیاری از کانال های رایج، می توان کدهایی یافت که داده ها را قابل اطمینان و با نرخ دلخواه R که کمتر از یک آستانه مشخص C ( ظرفیت کانال ) ، منتقل کنند. در واقع، احتمال خطای کدگشایی می تواند با افزایش طول کد ( N ) ، به طور نمایی کاهش یابد. اما، پیچیدگی یک کدگشایی بهینۀ ساده لوحانه هم - که تنها بر محاسبۀ درست نمایی ( likelihood ) هر کلمۀ کدِ فرستاده شدۀ ممکن، استوار است - به طور نمایی ( exponentially ) با طول کد ( N ) افزایش می یابد. بنابراین چنین کدگشایی بهینه ای، به سرعت ناممکن می شود.
دیو فورنی در پایان نامه دکترایش نشان داد که می توان از کدهای هم پیوسته برای دست یابی به احتمالات خطایی که به ازای همۀ نرخ های دادۀ کمتر از ظرفیت کانال، به طور نمایی کاسته می شوند، و از سوی دیگر، پیچیدگیِ کدگشایی شان، تنها به طور چندجمله ای ( polynomial - time ) با طول کد افزایش می یابد، بهره برد.
فرض کنید Cin یک کد باشد، یعنی یک کد بلوکی به طول n ، بعد k ، حداقل فاصله همینگ d ، و نرخ r = k/n ، روی الفبای A :
و Cout یک کد روی الفبای B با تعداد سمبول های B| =||A|k| باشد:
کد درونی Cin، یکی از |A|k = |B| ورودی های ممکن را می پذیرد، آن را به یک n - تایی روی A کد میکند، روی کانال می فرستد، و به یکی از |B| خروجی های ممکن کدگشایی می کند. این را می توان به عنوان یک فراکانال ( super channel ) در نظر گرفت که یک سمبل را از الفبای B منتقل می کند. از این کانال N بار برای انتقال هر یک از N سمبل در یک کلمه کد Cout استفاده می کنیم. بنابراین، هم پیوستگی Cout ( کد بیرونی ) با Cin ( کد درونی ) ، که با Cout∘Cin نشان داده می شود، کدی به طول Nn روی الفبای A است: [ ۱]
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفکدگذاری کانال، به فرستادن رشته ای از داده ها - با بیشترین نرخ ( سرعت ) ممکن - روی یک کانال مخابراتی مشخص، و سپس کدگشایی قابل اطمینان داده ها در گیرنده و به کمک الگوریتم های قابل پیاده سازیِ کدگذاری و کدگشایی می پردازد.
قضیه کدگذاری کانال شانون نشان می دهد که برای بسیاری از کانال های رایج، می توان کدهایی یافت که داده ها را قابل اطمینان و با نرخ دلخواه R که کمتر از یک آستانه مشخص C ( ظرفیت کانال ) ، منتقل کنند. در واقع، احتمال خطای کدگشایی می تواند با افزایش طول کد ( N ) ، به طور نمایی کاهش یابد. اما، پیچیدگی یک کدگشایی بهینۀ ساده لوحانه هم - که تنها بر محاسبۀ درست نمایی ( likelihood ) هر کلمۀ کدِ فرستاده شدۀ ممکن، استوار است - به طور نمایی ( exponentially ) با طول کد ( N ) افزایش می یابد. بنابراین چنین کدگشایی بهینه ای، به سرعت ناممکن می شود.
دیو فورنی در پایان نامه دکترایش نشان داد که می توان از کدهای هم پیوسته برای دست یابی به احتمالات خطایی که به ازای همۀ نرخ های دادۀ کمتر از ظرفیت کانال، به طور نمایی کاسته می شوند، و از سوی دیگر، پیچیدگیِ کدگشایی شان، تنها به طور چندجمله ای ( polynomial - time ) با طول کد افزایش می یابد، بهره برد.
فرض کنید Cin یک کد باشد، یعنی یک کد بلوکی به طول n ، بعد k ، حداقل فاصله همینگ d ، و نرخ r = k/n ، روی الفبای A :
و Cout یک کد روی الفبای B با تعداد سمبول های B| =||A|k| باشد:
کد درونی Cin، یکی از |A|k = |B| ورودی های ممکن را می پذیرد، آن را به یک n - تایی روی A کد میکند، روی کانال می فرستد، و به یکی از |B| خروجی های ممکن کدگشایی می کند. این را می توان به عنوان یک فراکانال ( super channel ) در نظر گرفت که یک سمبل را از الفبای B منتقل می کند. از این کانال N بار برای انتقال هر یک از N سمبل در یک کلمه کد Cout استفاده می کنیم. بنابراین، هم پیوستگی Cout ( کد بیرونی ) با Cin ( کد درونی ) ، که با Cout∘Cin نشان داده می شود، کدی به طول Nn روی الفبای A است: [ ۱]
wiki: کد تصحیح خطای هم پیوسته