فهرست مطالب:
فصل اول : کدهای بلوکی و کدهای کانولوشن
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 را ارضا کند .
- یافتن روشهای اجرایی ساده جهت انکدینگ و دیکدینگ این کدها .
پروژه آماده: بررسی انواع کدهای تصحیح کننده و کانولوشن و کدهای تصحیح کننده (97 صفحه فایل ورد - word)
