نظریه کدگذاری

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

مقدمه[ویرایش]

نظریه کدگذاری یا نظریهٔ رمزنگاری به بررسی روش‌های کدگذاری اطلاعات می‌پردازد و یکی از راه‌های حل مسئله در بخش‌های مختلف علوم (مثل نظریه اطلاعات، مهندسی برق، ریاضیات و علوم رایانه، انتقال داده) است؛ به این ترتیب که می‌توان با استفاده از آن روش‌های مطمئن برای انتقال داده‌ها طراحی کرد به‌طوری تکرارهای بی‌مورد کم و خطاها کاهش یابد.

نظریه کدگذاری در سال ۱۹۴۸ توسط ریچارد همینگ پایه‌ریزی شد. وی پی برده بود هنگامی که رایانه از یک عمل رایج نسخه‌برداری می‌کند و با عمل دیگری شروع به کار می‌کند، هرگز نمی‌تواند به حالت اولیه بازگردد. نظریه کدگذاری مثال قابل توجهی از ریاضی محض در حل مسائل علمی است. اگر چه برخی از رمزهای ساده دارای ساختاری هستند که نیاز زیادی به ریاضیات ندارند، با این حال ویژگی رمزها از کشفیات ریاضیات است. مانند هسته ارسال خطی که اثبات فعالیت‌های واقعی را ممکن می‌سازد و بدون این‌گونه برهان‌ها، رمزها در حقیقت بدون استفاده می‌باشند. علاوه بر این، ریاضیات موجب ایجاد رمزها در ابعاد دیگر می‌شود و با افزایش قابلیت تصحیح خطا، اثبات‌هایی را برای موجودیت یا عدم موجودیت رمزها ارائه داده‌است.

دسته‌بندی[ویرایش]

سه دسته کد وجود دارد:

۱: رمزگذاری منبع (فشرده‌سازی داده‌ها)

۲: رمزگذاری مسیر انتقال (تصحیح خطای انتقال)

۳: منبع اشتراکی و رمزگذاری مسیر انتقال

مورد اول، رمز نگاری منبع، تلاش دارد برای مؤثر تر انتقال دادن داده‌ها، آن‌ها را فشرده کند. مثال عملی آن هر روز در اینترنت، وقتی از پسوند zip برای انتقال فایل‌های مختلف استفاده می‌کنیم قابل مشاهده است. چرا که حجم مورد انتقال را کم کرده و ترافیک شبکه را کاهش می‌دهد. مورد دوم، رمزگذاری مسیر انتقال، بیت‌هایی را به داده‌ای مورد انتقال اضافه می‌کند تا آن‌ها را در اختلالات موجود در مسیر انتقال سالم به مقصد برساند. کار بر عادی ممکن است از کاربردهای معمول این نوع از رمز نگاری بی‌خبر باشد. برای نمونه یک CD معمولی از روش کدگذاری Reed-Solomon برای تصحیح خطای ناشی از خراش و غبار استفاده می‌کند. در این مثال مسیر انتقال داده خود CD خواهد بود! گوشی‌های همراه نیز از نوعی کدگذاری برای تصحیح خطای ناشی از محو شدگی سیگنال و مخابرهٔ رادیویی با فرکانس بالا، بهره می‌برد.

رمزگذاری منبع[ویرایش]

به‌طور ساده هدف این کار این است که داده‌های منبع را گرفته و آن را کوچکتر کند.

اصل[ویرایش]

انتروپی منبع میزان اطلاعات است. اساساً روش‌های کدگذاری منبع تکرار بی‌مورد را کم می‌کنند تا با بیت‌های کمتر اطلاعات بیشتری را منتقل کنند. فشرده‌سازی داده‌ها همان گونه که از نامش پیداست تلاش دارد که متوسط طول پیام‌های ارسالی را بر اساس یک مدل احتمالاتی فرضی و ویژه به نام entropy encodingکاهش دهد. تکنیک‌های متعددی که برنامه‌های فشرده ساز استفاده مکنند در تلاشند که به حد انتروپی منبع یعنی(C(x) ≥ H(x برسند؛ که در ان(H(x انتروپی منبع و(C(x انتروپی فایل پس از پردازش است. در موارد خاص هیچ روش کدگذاری برای منبع، بهتر از خود کد منبع نیست!

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

رمزگذاری مسیر انتقال: هدف این رمزگذاری یافتن کدهایی است که سریع تر منتقل می‌شوند، شامل تعداد زیادی کد واژهٔ صحیح هستند و می‌توانند خطاها را تصحیح کنند یا اینکه حد اقل تعداد زیادی از خطاها را تشخیص دهند. کارایی برنامه‌ها در این زمینه نوعی سبک و سنگین کردن نیاز دارد. به همین دلیل برنامه‌ها هر کدام کدهای متناسب خود را دارند. ویژگی‌های مورد نیاز برای هر کد بستگی به این دارد که در انتقال مربوط به آن کد احتمال وقوع چه خطاهایی وجود دارد، برای نمونه درمورد CDهای معمولی خطاهای رایج خراش‌ها و گرد و غبار هستند. پس داده‌ها روی سطح دیسک توزیع می‌شوند. به عنوان یک مثال نه چندان خوب از کد گذاری، کدگذاری تکراری ساده، مورد قابل فهمی از این روش است. در این روش یک بخش از بیت‌های منبع را گرفته و آن را سه بار می‌فرستیم. درمقصد، دریافت‌کننده این سه قسمت را گرفته و آن‌ها را بیت به بیت چک می‌کند، و آن مقداری را که برای هر بیت فراوانی بیشتری دارد به عنوان مقدار صحیح برمی‌گزیند. راه پیچیده‌تر آن است که بیت‌ها را کاملاً پشت سر هم نفرستیم. بلکه آن هارا برگ برگ کنیم. داده‌ها ابتدا به چهار دسته تقسیم می‌شوند، سپس در یک حلقه یک بیت از اولی، یک بیت از دومی و … را می‌فرستیم. این کار سه بار تکرار می‌شود تا جایی که داده‌ها روی سطح دیسک توزیع شوند. در مورد روش کدگذاری تکراری ساده شاید این روش مؤثر نباشد. اما کدهای شناخته شدی قدرتمندی وجود دارند که وقتی از روش برگ برگ کردن استفاده می‌شود، در تصحیح از هم پاشیدگی حاصل از خراش و غبار بسیار موثرند. کدهای دیگر برای کاربردهای دیگر مفیدند.

کدگذاری کانال[ویرایش]

عبارت نظریهٔ کدگذاری جبری زیر مجموعه‌ای از نظریهٔ کدگذاری را بیان می‌کند که در آن ویژگی‌های کدها با عبارات جبری بیان می‌شود. نظریهٔ کدگذاری جبری اساساً به دو دسته تقسیم می‌شود:

۱. کدهایی با بلوک‌های خطی.

۲. کدهای پیچشی (کانولوشن).

این نظریه سه ویژگی زیر از کدها را بررسی می‌کند:

۱. طول کد واژه‌ها

۲. تعداد کل کد واژه‌های قابل قبول

۳. حد اقل فاصلهٔ میان دو کد واژهٔ قابل قبول، بیشتر با استفاده از روش فاصلهٔ همینگ و در بعضی از موارد با استفاده از روش فاصلهٔ لی.

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

کدگذاری آنالوگ[ویرایش]

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

کار بردهای دیگری از نظریهٔ رمز نگاری[ویرایش]

غیر از آنچه که در بالا به آن اشاره شد، طراحی کد برای همگام سازی، از دیگر موارد مد نظر نظریهٔ کدگذاری است. یک کد می‌تواند طوری طراحی شود که به راحتی جابجایی فاز (موج) را تشخیص دهد و تصحیح کند و اینکه از یک مسیر چند سیگنال را بفرستد.

دیگر کاربرد کدها که در برخی از گوشی‌های همراه استفاده می‌شود، دسترسی چندگانه تقسیم کدی می‌باشد.

منابع[ویرایش]