پروژه آماده: بررسی انواع کدهای تصحیح کننده و کانولوشن و کدهای تصحیح کننده (97 صفحه فایل ورد - word)

فهرست مطالب:

فصل اول : کدهای بلوکی و کدهای کانولوشن

1-1- مقدمه :

1-2- ماکزیمم احتمال دیکدینگ  Maximum Likelihood Decoding

1-3­- انواع خطا Type of error

1-4- راه کارهای کنترل خطا  Error control Strategies

1-5- بررسی کدهای تصحیح کننده خطای برست (از هم پاشیدگی)  Burst –Error – Correcting Codes

1-6-دیکدینگ کدهای چرخشی تصحیح کننده خطای برست تکی

1-7- کدهای تصحیح کننده خطای برست تکی  Single – Burst – Correcting Codes

1-7-1-کدهای آتشین (Fire codes) :

1-8-سایر کدها :

1-9-کدهای یک در میان سازی  Interleaved Codes :

1-10-کدهای تصحیح خطای برست فاز بندی شده :  Phased – Burst-Error-Correcting

1-10-1- کدهای Burton

فصل دوم : کدهای تصحیح خطای رندم و برست  

2-1- کدهای محصول (Product)

2-2-کدهای    Reed-Solomon

2-3-کدهای بهم پیوسته ( متصل شده )   Concatenated Codes

2-4-تصحیح کدهای آتشی برای تصحیح همزمان خطاهای رندم و برست :

2-5- تصحیح خطای برست با کد های کانولوشن

2-6- کدهای کانولوشن تصحیح خطای برست

2-6-1- کدهای Berlekamp – Preparata

2-6-3-کدهای کانولوشن یک درمیان شده :

2-6-2-کدهای Iwadare-Messey

2-7-کدهای کانولوشن تصحیح کننده هردو خطاهای برست و رندم :      Burst – And-

2-7-1- کدهای پراکنده شده ( منتشر شونده Diffuse  )

2-7-2- سیستم جستجوی برست  ‏ The Burst Finding System

2-7-3-سیستم تله گذاری برست   The Burst-Trapping System

فصل سوم : کدهای تصحیح کننده پاک شدگی برست با تأخیر پائین

3-1-مقدمه :

3-2- ساختمان کد :

3-3-کدهای حداکثر کوتاه شده :

3-4-بررسی مجموع اغتشاش ها و گین های کدینگ :

فصل چهارم : یک الگوریتم طراحی شده جدید برای دیکدینگ کدهای

خلاصه :

4-1- مقدمه

4-2- انکدینگ کدهای RS :

4-3-دیکدینگ کدهای RS :

4-4- الگوریتم 1  کدهای RS :

تشریح عملیاتی بودن این الگوریتم :

4-5-الگوریتم   1a : دیکدینگ کدهای RS (تغییر یافته ):

4-6-تبدیل فوریه سریع   Fast Fourier Transforms (FFT)  :

– FFT‌ وفقی :

فصل پنجم : روش بسته بندی  پی در پی جهت دست یافتن به تکنیک یک درمیان سازی چند بعدی (M-D):

5-1- مقدمه :

5-2- آرایه های یک درمیان شده پایه :

رویه 4-1 :

5-3- آرایه پایه  دوبعدی مربع شده :

– آنالیز اجرای رویه فوق :

فصل ششم :  کد های محصول با افزونگی کاسته شده ، جهت تصحیح خطاهای

6-1-مقدمه :

6-2- ساختاری ساده ای با استفاده از کدهای کاسته شده افزونگی :

6-3- کاهش افزونگی بیشتر :

6-4-اضافه کردن تصحیح خطای ردیفی ( ساختار 3 )

مقدمه :

امروزه دو نوع عمومی از کدها استفاده می شود : کدهای بلوکی و کدهای کانولوشن . انکدینگ یک کد بلوکی را به تر تیبی از اطلاعات در قالب بلوکهای پیغام از k بیت اطلاعات برای هر کدام تقسیم می کند . یک بلوک پیغام با k مقدار باینری که بصورت u=(u1,u2,…,uk) نشان داده می شود ، یک پیغام نامیده می شود . در کدینگ بلوکی از سمبل u جهت نشان دادن k بیت پیغام از کل ترتیب اطلاعات استفاده می گردد .

تعداد کل بیت های پیغام متفادت موجود پیغام است . انکدر هر پیغام u را بطور غیر وابسته ، بصورت یک n تایی v=(v1,v2,…,vn) که کلمه کد (codeword) نامیده می شود ، ارسال می دارد . در کدینگ بلوکی سمبل v برای مشخص کردن سمبل بلوک از کل ترتیب انکد شده استفاده می گردد .

از پیغام قابل ساخت ، کلمه کد مختلف در خروجی انکدر قابل ایجاد است . این مجموعه کلمات کد با طول n یک کد بلوکی (n,k) نامیده می شود. نسبت R=k/n نرخ کد نامیده می شود . نرخ کد می تواند تعداد بیتهای اطلاعات که انکد می شود را در هر سمبل انتقال یافته ،محدود کند . در حالتیکه n سمبل خروجی کلمه کد که فقط به k بیت ورودی پیغام وابسته باشد ، انکدر را بدون حافظه (memory-less) گویند . انکدر بدون حافظه با ترکیبی از مدارات لاجیک قابل ساخت یا اجرا است . در کد باینری هر کلمه کد v باینری است . برای اینکه کد باینری قابل استفاده باشد ، بعبارت دیگر برای داشتن کلمات کد متمایز باید یا باشد . هنگامیکه k<n باشد ، n-k بیتهای افزونگی (redundant) می تواند به بیتهای یک پیغام اضافه گردد و کلمه کد را شکل دهد . این بیتهای اضافه شده توانایی کد را در مبارزه با نویز کانال فراهم می آورد . با نرخ ثابتی از کد ، بیت های افزونگی بیشتری را می توان با افزایش دادن طول بلوک n از کد ، با پیغام جمع کرد و این تا هنگامی است که نسبت k/n ثابت نگه داشته شود .

چگونگی انتخاب بیت های افزونگی تا اینکه ارسال قابل اطمینانی در یک کانال نویزی داشته باشیم از اصلی ترین مسائل طراحی یک انکدر است .

انکدر یک کد کانولوشن نیز به همان ترتیب ، k بیت بلوکی از ترتیب اطلاعات u را می پذیرد و ترتیب انکد شده ( کلمه کد ) v با n  سمبل بلوکی را می سازد . باید توجه کرد که در کدینگ کانولوشن سمبل های u و v جهت مشخص کردن بلوکهای بیشتر از یک بلوک استفاده می گردند . بعبارت دیگر هر بلوک انکد شده ای نه تنها وابسته به بلوک پیغام k بیتی متناظرش است ( در واحد زمان )‌ بلکه همچنین وابسته به m بلوک پیغام قبلی نیز می باشد . در این حالت انکدر دارای حافظه (memory ) با مرتبه m است .

محصول انکد شده ترتیبی است از یک انکدر k ورودی ، n خروجی با حافظه مرتبه m که کد کانولوشن (n,k,m) نامیده می شود . در اینجا نیز R=k/n نرخ کد خواهد بود و انکدر مذکور با مدارات لاجیک ترتیبی قابل ساخت خواهد بود . در کد باینری کانولوشن ، بیت های افزونگی برای تقابل با کانال نویزی می تواند در حالت k<n یا R<1  به ترتیب اطلاعات اضافه می گردد .

معمولاً k و n اعداد صحیح کوچکی هستند و افزونگی بیشتر با افزایش مرتبه حافظه از این کدها بدست می آید . و از این رو k و n و در نتیجه R ثابت نگه داشته می شود.

اینکه چگونه استفاده کنیم از حافظه تا انتقالی قابل اطمینان در یک کانال نویزی داشته باشیم ، از مسائل مهم طراحی انکدر ها محسوب می شود .

1-2– ماکزیمم احتمال دیکدینگ Maximum Likelihood Decoding

یک بلوک دیاگرام از سیستم کد شده در یک کانال AWGN با کوانتیزاسیون محدود خروجی در شکل 1 نشان داده شده است.

در این سیستم خروجی منبع u نشاندهنده پیغام k بیتی ، خروجی انکدر ، v نشاندهنده کلمه کد n- سمبلی خروجی دیمدولاتور ، r نشاندهنده آرایه Q دریافت شده n تایی متناظر و خروجی دیکدر نشاندهنده تخمینی از پیغام انکد شده k بیتی است . در سیستم کد شده کانولوشن ، u ترتیبی از kl بیت اطلاعات و v یک کلمه کد است که دارای N=nl+nm=n(l+m) سمبل می باشد . kl طول ترتیب اطلاعات و N طول کلمه کد است . سرانجام nm سمبل انکد شده بعد از آخرین بلوک از بیتهای اطلاعات در خروجی ایجاد می گردد . این عمل در طول m واحد زمانی حافظه انکدر انجام می پذیرد . خروجی دی مدولاتور ، r یک N تایی دریافت شده Q- آرایه ای است و خروجی یک تخمین از ترتیب اطلاعات می باشد. در واقع دیکدر می بایستی یک تخمین از ترتیب اطلاعات u براساس ترتیب دریافت شده r تولید نماید . پس یک تناظر یک به یک بین ترتیب اطلاعات u و کلمه کد v وجود دارد که دیکدر بر این اساس می تواند یک تخمین از کلمه کد v بدست آورد . روشن است که در صورتی است ، اگر و فقط اگر .

قانون دیکدینگ (یا برنامه دیکدینگ ) در واقع استراتژی انتخاب یک روش تخمین ، جهت تخمین کلمه کد از هر ترتیب دریافت شده ممکنr است . اگر کلمه کد v فرستاده شده باشد ، یک خطای دیکدینگ رخ داده است اگر و فقط اگر .

با دریافت r ، احتمال خطای شرطی دیکدر بصورت زیر تعریف می گردد : (1)

پس احتمال خطا دیکدر : (2) بدست می آید .

P(r) وابسته به قانون دیکدینگ نمی باشد . از این رو یک دستورالعمل دیکدینگ بهینه یعنی با حداقل P(E) باید را برای تمام مقادیر R به حداقل برساند .

به حداقل رسانیدن به مفهوم به حداکثر رسانیدن است . توجه گردد که اگر برای یک r دریافت شده با احتمال ماکزیمم انتخاب کردن ( تخمین ) از کلمه کد v به حداقل می رسد : (3) که شبیه ترین کلمه از r دریافت شده است . در صورتیکه تمام ترتیبات اطلاعات و درپی آن تمام کلمات کد مشابه باشند ، ( یعنی P( r ) برای تمام v ها یکسان باشد ) حداکثر کردن رابطه 3 معدل حداکثر کردن P(r|v) است . و برای یک DMC(Discrete memoryless channel) داریم :   (4)‌ .

باید توجه داشت که برای یک کانال بدون حافظه هر سمبل دریافت شده فقط به سمبل فرستاده شده متناظرش وابسته است . یک دیکدر که روش تخمینی جهت ماکزیمم کردن رابطه 4 انتخاب کند ، دیکدر با حداکثر احتمال نامیده می شود . MLD(Maximum Likelihood Decoder) – ماکزمم کردن رابطه 4 معادل ماکزمم کردن تابع احتمال لگاریتمی زیر است : (5)  بنابراین یک MLD برای یک DMC یک را بعنوان تخمینی از کلمه کد v برگزیند که رابطه 5 ماکزیمم گردد . درصورتیکه کلمات که معادل نباشد ، MLD لزوماً بهینه نمی گردد.

دراین حالت احتمالات شرطی P(r|v) باید بوسیله احتمالات کلمات کد P ( r) وزن داده شود تا مشخص گردد که کدام کلمه کد P(v|r) را ماکزیمم می کند .

اکنون مشخصه های MLD در یک BSC (Binary systematic Channel) مورد بررسی قرار می گیرد . در این حالت r  یک ترتیب باینری است که بغلت نویزی بودن کانال ممکن است از کلمه کد انتقال یافته v در بعضی موقعیت ها متفاوت باشد .

وقتی و بالعکس وقتی در نظر می گیریم . d(r,v) را فاصله بین rوv ( یعنی تعداد موقعیت های متفاوت بین rو v ) در نظر می گیریم . برای یک طول n یک کد بلوکی رابطه 5 بشکل زیر در می آید : (6)

. توجه گردد که برای کد کانولوشن n در رابطه 6 با N  بزرگ جایگزین می گردد .

در صورتیکه را برای P<1/2 و  ثابت برای تمام v ها ، در نظر بگیریم ، قاعده دیکدینگ MLD برای BSC ، را بعنوان کلمه کد v  انتخاب می کند که فاصله d(r,v) را بین rوv به حداقل برساند . بعبارت دیگر کلمه کدی را انتخاب می کند که در تعداد کمتری از موقعیتها از ترتیب دریافت شده ، متفاوت باشد . برای همین یک MLD برای BSC یک دیکدر با حداقل فاصله نامیده می شود .

تحقیقات Shannon در رابطه به بررسی توانایی کانال نویزی در ارسال اطلاعت تئوری کدینگ کانال نویزی را حاصل کرد و بیان می دارد که هر کانال دارای یک ظرفیت کانال C است و برای هر نرخ R<C ، کدهای ایجاد شده با نرخ R  با دیکدینگ ماکزیمم احتمال ، دارای کمترین احتمال خطای دیکدینگ P(E) است . در عمل برای هر R<C برای کدهای بلوکی با طول n داریم : (7) و برای کدهای کانولوشن با حافظه m : (8)  می باشد .

که طول اجباری کد نامیده می شود . و توابع مثبتی از R برای R<C هستند . که با پارامترهای کانال مشخص می گردند . مزر رابطه 7 بطور قرار دادی براین مطلب دلالت دارد که احتمالات خطای کوچک با کدینگ بلوکی R<C ثابت با افزایش طول n بلوک درحالتیکه نرخ k/n ثابت بماند ، بدست می آید . مرز رابطه 8 بیان می دارد که احتمالات خطای کوچک برای هر R<C  ثابت ، با افزایش طول یعنی با افزایش مرتبه حافظه m مادامیکه k و n ثابت باشند قابل دست یابی است . تئوری کدینگ کانال نویزی بر پایه یک استدلال ، کدینگ رندم نامیده می شود .

مرزهای بنا نهاده شده در واقع بر اساس احتمال خطای متوسط از مجموعه تمام کدها بدست می آید . مادامیکه کدها بهتر از حد متوسط شکل گیرند ، تئوری کدینگ کانال نویزی ، وجود کدها را در مرزبندی روابط 7 و 8 تضمین می نماید اما بیان نمی دارد که این کدها چگونه ساخته شوند .

برای دست یافتن به احتمالات خطای خیلی کمتر برای کدهای بلوکی با نرخ ثابت R<C طول های خیلی بزرگ از آن احتیاج است و در پی آن باید کلمات کد خیلی بزرگ باشد . و بعبارت دیگر هنگامیکه برای یک MLD  باید برای هر کد آن LogP(r|v) محاسبه گردد . سپس کلمه کدی که ماکزیمم باشد ، انتخاب گردد ، تعداد محاسبات برای شکل دادن یک MLD بسیار زیاد خواهد شد . برای کدهای کانولوشن ، احتمالات خطای کوچک به یک مرتبه m حافظه بزرگ محتاج است .

یک MLD برای کدهای کانولوشن به تقریباص محاسبه برای دیکد کردن هر بلوک از k بیت اطلاعات احتیاج دادرد و این محاسبات با افزایش m زیاد می شود . از این رو با استفاده از دیکدینگ با ماکزیمم احتمال جهت دستیابی به احتمالات خطای پائین غیر عملی به نظر می رسد . لذا دو مشکل اساسی جهت دستیابی به احتمالات خطای پائین مورد نیاز است :

ساخت کدهای طولانی خوب با استفاده از دیکدینگ ماکزیمم احتمال که مرزهای روابط 7 و 8 را ارضا کند .یافتن روشهای اجرایی ساده جهت انکدینگ و دیکدینگ این کدها .