كدهای بلوكی و كدهای كانولوشن

دسته: کامپیوتر و IT
بازدید: 167 بار
فرمت فایل: doc
حجم فایل: 2058 کیلوبایت
تعداد صفحات فایل: 32

كدهای بلوكی و كدهای كانولوشن امروزه دو نوع عمومی از كدها استفاده می شود كدهای بلوكی و كدهای كانولوشن انكدینگ یك كد بلوكی را به تر تیبی از اطلاعات در قالب بلوكهای پیغام از k بیت اطلاعات برای هر كدام تقسیم می كند یك بلوك پیغام با k مقدار باینری كه بصورت u(u1u2…uk) نشان داده می شود ، یك پیغام نامیده می شود در كدینگ بلوكی از سمبل u جهت نشان داد

قیمت فایل فقط 1,800 تومان

سمه تعالی

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

1-1- مقدمه :

امروزه دو نوع عمومی از كدها استفاده می شود : كدهای بلوكی و كدهای كانولوشن . انكدینگ  یك كد بلوكی را به تر تیبی از اطلاعات در قالب بلوكهای پیغام از 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

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

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

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

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

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

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

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

شكل 1- سیستم codec  در یك كانال AWGN

در این سیستم خروجی منبع 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

كه  طول اجباری كد نامیده می شود .  و  توابع مثبتی از R برای R

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

برای دست یافتن به احتمالات خطای خیلی كمتر برای كدهای بلوكی با نرخ ثابت R

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

1-    ساخت كدهای طولانی خوب با استفاده از دیكدینگ ماكزیمم احتمال كه مرزهای روابط 7 و 8 را ارضا كند .

2-    یافتن روشهای اجرایی ساده جهت انكدینگ و دیكدینگ این كدها .

تعریف 1 : كدهای همینگ : كدهایی هستند كه می توانند یك خطا را تصحیح كنند و دارای مشخصات زیر می باشند (به ازاء هر عدد صحیح  )‌ : 1- طول كد :   2- تعداد بیت های پیغام :   3- تعدا بیت های پریتی :   4- این كدها قدرت تصحیح یك خطا را دارند :

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

در كانالهای بدون حافظه ، نویز بر هر سمبل ارسال شده بدون وابستگی اثر می گذارد . بعنوان مثال در یك BSC هر بیت انتقال یافته  دارای احتمال P از دریافت شده های غیر صحیح و 1-P  از دریافت شده های صحیح است كه غیر وابسته به سایر بیتهای ارسال شده می باشد . از این رو خطا ها بصورت رندم در ترتیب دریافت شده رخ می دهد و بنابراین كانالهای بدون حافظه كانالهای با خطای رندم نامیده می شوند .

مثال خوبی از این كانالها كانالهای ماهواره ای و كانال های با فضای ایستاده است . در واقع اكثر انتقالات به خط مستقیم دارای خطا های رندم هستند . كدهایی كه جهت تصحیح خطاهای رندم تعبیه می شوند ، كدهای تصحیح خطای رندم نامیده می شوند .

شكل2- دیاگرام احتمال گذار a- كانال سیستماتیك باینری b – كانال بدون حافظه گسسته

با كانالحافظه دار ، نویز غیر وابسته از انتقالی به انتقال دیگر نمی باشد . یك مدل ساده از كانال حافظه دار در شكل 3 نشان داده شده است . این مدل شامل دو حالت است . یك حالت خوب  كه در هر انتقال خطاها بطور غیر تكراری رخ می دهد . و  و یك حالت بد كه در هر انتقال خطاها دارای ماكزیمم احتمال  است . كانال در اكثر موارد در حالت خوب است اما در حالت شیفت به حالت بد در مواقع تغییر پارامترهای انتقال كانال ( مثلاً در حالت محوشوندگی عمیق كه در اثر چند مسیرگی رخ می دهد ) ، انتقال خطاها در دسته ها (cluster)و ازهم پاشیدگی ها (burst) رخ می دهد كه علت آن افزایش احتمال گذر در حالت بد است و كانال های با حافظه ، كانالهای دارای خطای از هم پاشیدگی (burst) نامیده می شوند .

مثالهایی از كانالهای دارای خطای برست ، كانالهای رادیویی است كه این خطا سبب محوشوندگی سیگنال درطول انتقال چند مسیره می گردد . محوشوندگی همچنین ممكن است در سیم یا كابل انتقال در اثر نویز سوئیچینگ یا مكالمه متقابل ایجاد می گردد . كدهایی كه جهت تصحیح این نوع خطاها بكار می رود به كدهای تصحیح كننده خطای برست معروفند (burst-error correcting codes) سرانجام بعضی از كانالهای تركیبی از هر دو خطای رندم و از هم پاشیدگی را دارا هستند و كانالهای مركب نامیده می شوند و كدهای تصحیح كننده این نوع خطا ها نیز كدهای تصحیح كننده خطای برست – رندم نامیده می شوند .

شكل3- مدل ساده ای از یك كانال با حافظه

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

بلوك دیاگرام نشان داده شده در شكل 4 یك سیستم یك مسیره را نشان می دهد . این ارتباط در واقع در یك جهت از فرستنده به گیرنده است

شكل 4- بلوك دیاگرام از یك نوع سیستم ذخیره سازی و انتقال اطلاعات

. كنترل خطا برای یك سیستم یك مسیره با استفاده از تصحیح خطای رو به جلو FEC(Forward Error Correction)  انجام می پذیرد كه بطور اتوماتیك خطاهای آشكار شده در گیرنده را تصحیح می كند .

مانند سیستم های ارتباطی فضایی كه تجهیزات انكدینگ ساده ای می تواند روی بدنه فضاپیما قرار داده شود اما تجهیزات انكدینگ پیچیده ای روی ایستگاه زمینی قرار داده می شود . بیشتر سیستم های كد كننده امروزی از فرمهای مختلفی از FEC استفاده می كنند ، حتی در مواردیكه سیستم یك مسیره نیست .

در موارد دیگری یك سیستم ارسال می تواند دو مسیره باشد . بدین معنا كه اطلاعات می تواند در هر دو جهت ارسال گردد و فرستنده نیز مانند یك گیرنده عمل كند ( ارسال و دریافت كننده transceiver)

مثالهایی از این نوع سیستم ها مانند كانالهای تلفنی و بعضی ارتباطات ماهواره ای می باشد . كنترل خطا برای یك سیستم دو مسیره می تواند با استفاده از آشكارسازی خطا و دوباره ارسال صورت پذیرد. كه به آن تكرار تقاضای اتوماتیك ARQ(Automatic Repeat Request) می گویند . در یك سیستم ARQ هنگامیكه خطاها در گیرنده آشكار می شود ، یك تقاضا برای تكرار پیغام به فرستنده ارسال می گردد و این مادامی است كه پیغام بطور صحیح دریافت شده باشد . دو نوع سیستم ARQ وجود دارد : ARQ با حالت توقف – انتظار و ARQپیوسته  .

با حالت اول ، فرستنده یك كلمه كد را به گیرنده می فرستد و منتظر می ماند تا یك پاسخ (acknowledg) مثبت (ACK) یا منفی (NAK) از گیرنده دریافت كند . درصورتیكه (ACK) دریافت شد ، مفهوم آن این است كه هیچ خطایی در گیرنده آشكار نشده است و فرستنده كلمه بعدی را ارسال می كند .

اگر NAK دریافت شود مفهوم آن این است كه در گیرنده خطا آشكار شده است و فرستنده همان كلمه كد را دوباره می فرستد . با وجود نویز این دوباره ارسال كردن ها ممكن است چندین بار تكرار گردد .

با ARQ پیوسته ، فرستنده كلمات را بطور پیوسته می فرستد و گیرنده نیز پاسخ را بطور پیوسته ارسال می كند . با دریافت یك NAK فرستنده شروع به دوباره ارسال می كند . در این حالت ممكن است یك كلمه كد را به خطا برگرداند و دوباره بفرستد . این حالت را GO – BACK-NARQ می نامند .

همچنین درحالتی ممكن است فرستنده كلمه كدی كه NAK داشته است را دوباره ارسال نماید . كه این حالت به Selective-Request ARQ نامیده می شود . ARQ با تكرار حساس موثرتر از حالت قبل است اما به مدارات لاجیك و بافر بیشتری احتیاج دارد.

در كل ARQ حالت پیوسته از ARQ توقف – انتظار موثر تر است اما در عین حال گرانتر می باشد . در ارتباطات ماهواره ای كه نرخ ارسال و نیز تاخیر آن طولانی است ، ARQ حالت پیوسته بطور نرمال استفاده می شود و ARQ حالت توقف – انتظار در سیستمی بكار می رود كه  زمان ارسال كلمه كد طولانی تر از زمان دریافت پاسخ باشد و بیشتر برای كانال های HALF-DUPLEX و ARQ  پیبوسته بیشتر برای كانال های FULL-DUPLEX  بكار می روند .

مزیت مهم ARQ بر FEC  این است كه آشكار سازی خطا به تجهیزات دیكدینگ ساده تری از تصحیح خطا نیاز دارد . همچنین ARQ در دوباره ارسال كردن اطلاعات هنگامیكه خطایی رخ می دهد ، حساسیت بیشتری دارد . بعبارت بهتر هنگامیكه نرخ خطای كانال بیشتر باشد ، ددوباره ارسال با تكرار بیشتری باید انجام پذیرد .و در این حالت ARQ دارای تاثیر كمتری می شود . در این موارد تركیبی از FEC و ARQ تاثیر بیشتری دارد كه به روشهای Hybrid معروف است .

تعریف2 : سیندرم و تشخیص خطا : یك كد بلوكی (n,k)  كه ماتریس پریتی چك آن ، H باشد ، فرض می گیریم . اگر یك كلمه كد از این كد روی كانال ارسال گردد ، كلمه دریافتی بصورت ذیل است :  ( r كلمه دریافتی ، u كلمه ارسالی و e بردار خطا است ) در این روش تعداد  كد خطا قابل تشخیص  است . و داخل این پترن ها ، تمامی پترن هایی كه d-1 یا كمتر خطا باشد ، قرار می گیرد. عمل تشخیص خطا توسط سیندرم صورت می پذیرد :  . اگر  (یعنی كلمه كد مجاز باشد ) خواهیم داشت : S=0  و در غیر اینصورت :  . پس جهت تشخیص داریم : 1- به ازای كلمه دریافتی سیندرم محاسبه می شود 2- اگر  خطا اعلام می شود و در غیر اینصورت خطا وجود ندارد و یا قابل تشخیص نیست .

تعریف 3-  كد های چرخشی : چند جمله ای مولد این كد ها :  . اگر   چند جمله ای پیغام باشد ، در اینصورت كلمه كد  با چند جمله ای مولد مذكور ، قابل تولید است .

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

همانگونه كه ذكر گردید كانالهایی وجود دارد كه تحت تاثیر اختلالات دسته ای (cluster) و ازهم پاشیدگی (burst) هستند .

مثلاً در خطوط تلفن  یك ضربه یا اختلال الكتریكی ممكن است باعث ایجاد خطاهای گروهی می گردد .

و در این حالت كدهای تصحیح كننده خطای رندم موثر نمی باشد . كدهای چرخشی در آشكار سازی و تصحیح خطای برست موثراند . از جمله این كدها كدهای آتشی (Fire Codes) است .

- معرفی : یك برست با طول l بعنوان یك بردار تعریف می گردد كه اجزاء غیر صفر آن به l موقعیت دیجیت های متوالی منحصر شده اند و اولین و آخرین آن غیر صفر است . مثلاً بردار خطای e=(000010110100000) یك برست با طول 6 را مشخص می كند . یك كد خطی كه توانایی تصحیح تمام خطاهای برست با طول l یا كمتر را داشته باشد اما تمام خطاهای برست با طول l+1 را نتواند تصحیح كند ، به این چنین كدی ، كد تصحیح كننده  برست l  گویند و یا كدی كه دارای توانایی تصحیح l خطای برست است .  روشن است كه برای كد (n,k) با l تصحیح خطای برست ، n-k  افزونگی قابل اضافه كردن است .

تئوری 1 -  یك شرط لازم برای كدهای خطی (n,k) كه بتواند  تمام خطاهای برست با طول l یا كمتر را تصحیح كند این است كه هیچ  برستی با طول 2l یا كمتر نتواند یك بردار كد را حاصل كند.

تئوری 2 – تعداد دیجیت های پریتی چك یك كد خطی (n,k) كه دارای برست با طول b یا كمتر بعنوان یك بردار كد نباشد ، حداقل b است . یعنی  است .

از تئوری های 1 و 2 در می یابیم كه محدودیتی روی تعداد دیجیتهای پریتی چك یك كد تصحیح خطای برست l وجود دارد .

تئوری3-  تعداد دیجیت های پریتی چك یك كد تصحیح خطای برست l باید حداقل 2l باشد كه داریم : (9)    .

تئوری 3 نشان می دهد كه توانایی تصحیح خطای برست یك كد (n,k) حداكثر [(n-k)/2] است . پس (10)   است .

این مرز فوقانی توانایی تصحیح خطای برست است و مرز Reiger نامیده می شود . و كدهایی كه به این مرز برسند بهینه هستند . نسبت (11) z=2l/(n-k) بعنوان معیاری جهت اندازه گیری كارایی تصحیح خطای برست توسط كد استفاده می گردد . یك كد optimal ( بهینه ) دارای z=1  است . باید متذكر شویم كه درصورت تصحیح تمام خطاهای برست با طول l یا كمتر و نیز آشكارسازی تمام خطاهای برست  توسط كد (n,k) ، تعداد دیجیتهای پریتی چك باید حداقل l+d  باشد .

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

decoding of Single-Burst-error-Correcting Cyclic Codes

این كدها بسادگی با تكنیك تله گذاری خطا  (trapping) قابل دیكد هستند . فرض شود كه كلمه كد v(x) از یك چرخشی

n,k)) با تصحیح خطای برست l انتقال یافته است . درصورتیكه r(x) و e(x) به ترتیب بردارهای دریافت شده و خطا باشند ،

 سیندرم r(x) است .

اگر خطاها در e(x) به موقعیت دیجیتهای پریتی چك با مرتبه بالا l  محدود گردد و چنانچه  از r(x) ، سپس دیجیت های سیندرم با مرتبه بالای l ،  با خطاهای e(x) سازگار است . و n-kl دیجیت سیندرم مرتبه پائین ،   صفر خواهد بود .

فرض كنید خطاها در e(x) به موقعیت های  از r(x) ، محدود باشد . ( شامل مواردی در حوالی انتها ) سپس بعد از تعداد مشخص از شیفت های چرخشی r(x)  ، i شیفت چرخشی ، خطاها در موقعیت های  از    شیفت یابند كه iامین شیفت از r(x)  است .

در صورتیكه  سیندرم حالت   باشد ، سپس اولین دیجیت با مرتبه بالای l از  با خطاها در موقعیت های  از    سازگار است و n-k-l دیجیت از  مرتبه پائین صفر خواهد بود . با این تكنیك می توانیم خطاها را در رجیستر سیندرم با سیكل چرخشی r(x) محدود (trap) كنیم . یك دیكدر محصوركننده خطا برای كد چرخشی تصحیح كننده خطای برست l در شكل 5 آمده است .

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

در این شكل بردار دریافت شده به رجیستر سیندرم از انتهای سمت چپ شیفت می یابد . عملكرد این دیكدر بطور خلاصه در مراحل ذیل تشریح شده است :

مرحله 1 – بردار دریافت شده r(x) به داخل  رجیشترهای سیندرم و بافر به طور همزمان شیفت می یابند و سیندرم s(x) شكل می یابد .

مرحله 2 – رجیستر سیندرم با روشن شدن گیت 2 شروع به شیفت می كند . به محض اینكه n-k-l مرحله سمت چپ رجیستر فقط شامل صفرها شود ، l مرحله سمت راست آن ، پترن خطای برست خواهد بود و از اینجا تصحیح خطا شروع می گردد.. 3 مرحله جهت انجام این كار باید انجام پذیرد .

مرحله 3 – اگر n-k-l مرحله سمت چپ رجیستر سیندرم شامل تمام صفر باشد بعد از i امین شیفت برای  ، خطای برست ، e(x) به موقعیت های پریتی چك r(x) محدود می شوند . در این حالت k دیجیت اطلاعات دریافت شده در رجیستر بافر ، خطای آزاد (error-free)  هستند .

سپس گیت 4 فعال شده و k  دیجیت اطلاعات خطای آزاد در بافر به data sink شیفت می یابد .

اگر n-k-l سمت چپ ترین مرحله از رجیستر سیندرم هرگز شامل تمام صفر در طول اولین شیفت n-k-l از رجیستر سیندرم نشود ، خطای برست شامل موقعیت های n-k پریتی چك از r(X) نخواهد شد .

مرحله 4 –  اگر n-k-l مرحله سمت چپ رجیستر سیندرم شامل تمام صفر باشد بعد از( (n-k-l+iامین شیفت از رجیستر سیندرم برای  باشد ، خطای برست به موقعیت های  از r(x) محدود می شود . ( این یك برست در محدوده انتها است ) در این حالت ، دیجیتهای l-i در سمت راست ترین l-i مرحله شیفت رجیستر با موقعیتهای
 از r(x) سازگار است و i دیجیت در مرحله i بعدی از رجیستر سیندرم با موقعیتهای خطادر  از r(x) سازگار می شود . در این لحظه یك كلاك شروع به شمارش از n-k-l-i+1 كرده و رجیستر سیندرم با گیت 2 خاموش شیفت می یابد .

بمحض شمارش كلاك تا n-k ، سمت راست ترین دیجیت در رجیستر سیندرم با موقعیتهای   از r(x) سازگار می شود . گیتهای 3 و 4 در ادامه فعال شده و دیجیتهای اطلاعات دریافت شده از رجیستر بافر بازخوانی می گردند . و با شیفت خطا  از رجیستر سیندرم تصحیح می گردد .

مرحله 5 – اگر n-k-l سمت چپ ترین مرحله از رجیستر سیندرم در زمان شیفت n-k بار رجیستر سیندرم ، هرگز تمام صفر نباشد ، دیجیتهای اطلاعات دریافت شده از رجیستر بافر با هر بار فعال شدن گیت 4 بازخوانی می گردد .

در زمان مشابه ، رجیستر با فعال شدن گیت 2 ، شیفت می یابد . بمحض اینكه سمت چپ ترین n-k-l از رجیستر سیندرم شامل تما صفر شود . در این حالت دیجیتها در سمت راست ترین l مرحله از رجیستر سیندرم سازگار می شود با دیجیتهای اطلاعات دریافت شده l بعدی كه از رجیستر بافر می آید .

گیت 3 سپس فعال شده و دیجیت های دارای خطا بوسیله دیجیت هایی كه از رجیستر سیندرم می آیند با غیر فعال شدن گیت 2 تصحیح می گردند .

اگر n-k-l مرحله از رجیستر سیندرم هرگز شامل تمام صفر نباشد ، در زمانی كه دیجیت های k اطلاعات از بافر خوانده می شوند ، یك خطای برست غیر قابل تصحیح آشكار شده است . با دیكدر فوق‌ ، پراسس دیكدینگ 2n كلاك زمان می برد و اولین سیكل n  كلاكی چرخشی جهت محاسبه سیندرم و n كلاك چرخشی بعدی جهت مسدود كردن خطا (trap) و تصحیح آن مورد نیاز است . باید توجه داشت كه n  كلاك چرخشی جهت محاسبه سیندرم بطور همزمان با پذیرش بردار دریافت شده از كانال است و هیچ زمان تاخیری در این عملكرد پیش نمی آید . اما دومین n كلاك چرخشی جهت مسدود كردن و تصحیح خطا ، تاخیر دیكدینگ را باعث می شود . در این دیكدر بردار دریافت شده به داخل رجیستر سیندرم از انتهای سمت چپ شیفت می یابد . اگر بردار دریافت شده به داخل رجیستر سیندرم از انتهای سمت راست شیفت یابد ، عملكرد دیكدر متفاوت خواهد شد . باید توجه كرد كه این دیكدر تنها خطاهای برست با طول l یا كمتر را تصحیح می كند . تعداد این پترن های خطای برست  است كه برای n بزرگ تنها بخش كوچك از پترن خطا قابل تصحیح خواهد بود . همچنین می توان دیكدر را به طریقی تغییر داد كه تمامی خطاهای برست با طول l+1 تا n-k یا كمتر را تصحیح كند . این تغییر بصورت ذیل است :

تمام بردارهای دریافت شده ابتدا به داخل رجیستر سیندرم شیفت می یابد و قبل از شكل دادن تصحیح خطا ، رجیستر سیندرم n بار بطور چرخشی شیفت یابد . ( با استفاده از ارتباطات فیدبك )‌ در طول این چرخش‌، طول b از كوتاه ترین برست در سمت راست ترین b مرحله از رجیستر سیندرم ظاهر می شود ، بوسیله یه شمارنده ضبط می گردد . این برست را فرض می كنیم بوسیله كانال به خطای برست افزوده شده است . با اتمام این شیفت قبل از تصحیح ، دیكدر به پراسس تصحیح می پردازد و رجیستر سیندرم دوباره شروع به شیفت می كند .

بمحض ظهور كوتاه ترین برست در سمت راست ترین مرحله از رجیستر سیندرم ، دیكدر شروع به تصحیح بطور عادی می كند .

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

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

 كدهای آتشی اولین كلاس  از كدهای چرخشی است كه بطور سیستماتیك جهت تصحیح خطاهای برست ساختار یافته اند . در صورتیكه ‍P(x) یك چند جمله ای با درجه m  در GF(2) باشد ، و p كوچكترین عدد صحیحی باشد كه P(x) قابل تقسیم بر

 گردد ، عدد صحیح p ، پریود P(x)  نامیده می شود . l را عدد صحیح مثبت   در نظر می گیریم كه 2l-1  قابل تقسیم بر l نباشد ، بك كد آتشی تصحیح كننده خطای برست از چند جمله ای زیر ایجاد می گردد : (13)   ، طول n از این كد كوچكترین عامل مشترك از 2l-1 و پریود p از P(x)  است : (14) n=LCM(2l-1,p)  تعداد  دیجیت های پریتی چك از این كد ، m+2l-1 است . توجه شود كه فاكتور  و P(x) از g(x) وابسته اولیه هستند .

می توان اثبات كرد كه كد آتشی تولید شده بوسیله چند جمله ای رابطه 13 در واقع توانایی تصحیح هر خطای برست با طول l یا كمتر را داراست . كدهای آتشی نیز می توانند توسط مدار مسدود كننده خطا (trapping) دیكد گردند . در یك سیستم انتقال دیتا  یا ذخیره سازی اگر گیرنده دارای  بعضی توانایی های محاسبه باشد ، یك دیكدر سریع جهت دیكد كدهای آتشین می توان بكار گرفت . نمونه ای از دیكدر مسدود كننده خطای برست با سرعت بالا توسط كدهای آتشی در شكل 6 آمده است .

شكل 6 – دیكدر مسدود كننده خطا با سرعت بالا برای كدهای اتشی

این دیكدر دارای دو رجیستر سیندرم است : یكی رجیستر پترن خطا و دیگری رجیستر محل خطا نامیده می شود . ارتباطات فیدبك از رجیستر پترن خطا برپایه فاكتور  از رجیستر محل خطا بر پایه فاكتور P(x) می باشد . چند جمله ای دریافت شده r(x) در ابتدا در دو رجیستر سیندرم و رجیستر بافر بازخوانی می شوند . بمحض ورود r(x) به داخل رجیسترهای سیندرم ، s1(x),s2(x) شكل می گیرند . دیكدر ،  s1(x) را چك می كند . اگر s1(x)=s2(x)=0  شد ، دیكدر ، چندجمله ای r(x) را دارای خطای آزاد فرض می كند . اگر  یا بلعكس گردد ، r(x)  قابل آشكارسازی است .اما خطاهای برست غیر قابل تصحیح خواهند بود و بنابرای دورانداخته می شوند . و اگر   سپس فرض می شود كه دارای خطای برست قابل تصحیح است و دیكدر شروع به پراسس تصحیح خطا می كند . پراسس تصحیح خطا در مرجع [1] آمده است.

با توجه نحوه پراسس ( كم شدن تعداد سیكل ها ) ، سرعت دیكدینگ بهبود خواهد یافت و این به قیمت لاجیك بیشتر برای این دیكدر است .

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

در كنار كدهای آتشی ، بعضی كدهای موثر چرخشی و كدهای چرخشی كوتاه شده برای تصحیح خطای برست تكی بكار می رود كه از راه محاسبه یا اجرای برنامه های كامپیوتری قابل دستیابی هستند . لیستی از این كدها به همراه چند جمله ایهای مولد مربوطه و نیز توانایی تصحیح خطای برست توسط آنها در جدول 1 آمده است :

جدول1 : بعضی كدهای چرخشی تصحیح كننده خطای برست و كدهای چرخشی كوتاه شده :

چند جمله ای مولد g(x)*	توانایی تصحیح خطای برست l	(n,k) code	n-k-2l
35 171 721 2467 1151 14515 47343 214537 1647235 2671	2 3 4 5 4 6 7 8 9 5	(7,3) (15,9) (15,7) (15,5) (19,11) (21,9) (21,7) (21,5) (21,3) (27,17)	0
15173 114361 224531 1505773 4003351 65 171 1663 7707	6 7 8 9 10 2 3 4 5	(34,22) (38,24) (50,34) (56,38) (59,39) (15,10) (21,14) (21,12) (21,10)	1
471 123 161 3551 13627 13617 6647133 3501	3 2 2 4 5 5 9 4	(17,9) (21,15) (31,25) (31,21) (35,23) (39,27) (41,21) (51,41)	2
…	…	…	…

* : چند جمله ایهای مولد بصورت هشت تایی (octal) نشان داده شده اند . هر دیجیت آن 3 دیجیت باینری بصورت كد زیر تولید می كند : 0(000),1(001),2(010),…,7(111) دیجیت های باینری حاصل سپس ضرایب چند جمله ای خواهند بود .

برای مثال نمایش باینری 171 برابر 001111001 است و چندجمله ای متناظر با آن :   

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

اگر یك كد چرخشی (n,k)  دارای ساختار  باشد ، بدین مفهوم كه  بار طولانی شود یا  بار دیجیت های اطلاعات با یك درمیان سازی افزایش یابند . این عمل بطور ساده با مرتب كردن ( دوباره چیدن )  بردار كد در كد اصلی در   ردیف

از یك آرایه مستطیلی و سپس انتقال ستون های آن به ستون های مجاور قابل اجراست . حاصل ان یك كد یك درمیان شده نامیده می شود كه دارای درجه  است .

شكل7- انتقال از یك كد یك در میان شده (interleaved)

مشهود است كه یك پترن از خطاها می توانند برای تمام آرایه ها تصحیح گردد اگر وفقط اگر پترن خطاها در هر ردیف ، پترن قابل تصحیح برای كد اصلی باشد . در این بین فرقی نمی كند كه یك برست با طول   - كه بیشتر از یك دیجیت در هر ردیف است – باشد . بنابراین اگر كد اصلی خطاهای تكی را تصحیح كند . كد یك در میان شده برست های تكی با طول  یا كمتر را تصحیح خواهند كرد و اگر كد اصلی برست تكی با طول l  یا كمتر را تصحیح كند ، كد یك درمیان شده هر برست تكی با طول
l  یا كمتر را تصحیح خواهد كرد . درصورتیكه یك كد (n,k) دارای حداكثر توانایی تصحیح خطای برست ممكن
(‌یعنی n-k-2l=0) باشد كد  یك در میان شده  توانایی ماكزیمم تصحیح خطای برست ممكن را دارا خواهد شد . بنابرای تكنیك یك درمیان سازی (Interleaving) مشكل جستجوی كدهای طولانی موثر تصحیح خطای برست را كاهش می دهد . برای نشان دادن طریقه تولید یك كد یك درمیان شده ، به بررسی عملكرد آرایه ها در انكدینگ و دیكدینگ احتیاج است كه یك نمونه موثر و نوین این تكنیك در فصول آینده تشریح شده است . بطور نمونه اگر چند جمله ای مولد از كد اصلی g(x)  را در نظر بگیریم چند جمله ای مولد كد یك درمیان شده ،    خواهد شد . محاسبات انكدینگ و سیندرم می تواند بوسیله شیفت رجیسترها صورت پذیرد كه در این حالت هر مرحله رجیستر دیكدر اصلی با  مرحله جایگزین می گردد . تكنیك یك درمیان سازی علاوه بر تصحیح خطاهای برست تكی برای تصحیح خطاهایرندم – برست نیز بهینه است .

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

یك كد (n,k) كه طول n بیت آن ضریبی از m باشد ، درنظر می گیریم :   .    دیجیت از هر بردار ممكن است به   زیر بلوك ، كه هر زیر بلوك نیز شامل m  دیجیت كد متوالی است ، گروه بندی گردد . بعنوان مثال    یك بردار كد است . سپس i امین زیر بلوك شامل دیجیتهای پشت سرهم :    خواهد بود .  

یك برست باطول  یا كمتر ، یك برست فازبندی شده نامیده می شود . اگر و فقط اگر به  زیر بلوك پشت سر هم محدود شده باشد . (‌ عدد صحیح مثبت كوچكتر از   است ) . یك كد خطی  كه توانایی تصحیح تمام خطاهای برست فاز بندی شده محدود به  یا كمتر زیر بلوك را داشته باشد ، كد تصحیح خطای برست فاز بندی شده   نامیده می شود . روشن است كه یك كد تصحیح خطای برست فازبندی شده   توانایی تصحیح هر برست تكی با طول   یا كمتر را داراست . بنابراین هر كد تصحیح خطای برست فازبندی شده  می تواند بعنوان یك كد تصحیح خطای برست تكی    استفاده می گردد .

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

این كدها زیر كلاسی از كدهای چرخشی تصحیح خطای برست فازبندی شده هستند و شبیه كدهای آتشی می باشند . درصورتیكه P(x) یك چند جمله ای غیر قابل ساده شدن از درجه m و پریود p باشد و n كوچكترین مضرب مشترك از m و p و  باشد ، برای هر عدد صحیح m یك كد Burton تصحیح كننده خطای برست m فازبندی شده با طول   با چند جمله ای زیر قابل ایجاد است : (15)    . تعداد دیجیت های پریتی چك این كد 2m است . پساین كد در واقع یك كد چرخشی  خواهد بود .هر بردار كد آن شامل  زیر بلوك می شود .

دیكدینگ یك كد Burton نیز می تواند با استفاده از یك دیكدر مسدود كننده خطا انجام پذیرد . دراین حالت محتویات m مرحله سمت چپ از رجیستر سیندرم باید تست گردد . كه در هر m امین شیفت صفر شده است یا خیر . همچنین می توان از روش یك درمیان سازی برای این كدها سود برد . برای این منظور بردارهای كد  را در كد تصحیح خطای برست فازبندی شده m  و در ردیف های از یك آرایه مستطیلی می چینیم . این آرایه دارای  ستون خواهد بود كه هر ستون شامل  زیر بلوك است . آرایه سپس از یك ستون به ستون مجاور در زیر بلوك و دریك ردیف انتقال می یابد . و درنهایت كد یك درمیان شده شامل  زیر بلوك خواهیم داشت . درصورتیكه از این كد جهت تصحیح خطای برست  استفاده گردد ، توانایی تصحیح  خطای برست برابر خواهد شد با :  . این نسبت برای كدهای Burton برابر z=1  است .

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

Burst-And_Random_Error-Correcting Codes

در بسیاری از كانالهای مخابراتی خطا به هر دو شكل برست و رندم رخ می دهد . و بنابراین كدهای تصحیح كننده هر كدام به تنهایی ناكارآمد خواخژهد شد . با یكدرمیان سازی یك كد تصحیح كننده خطای رندم t  ، (n,k)  با درجه  ، یك كد    كه توانایی هر تركیبی از t برست با طول  یا كمتر را داراست ، خواهیم داشت . مثالهایی از این نوع كدها در زیر آورده شده است :

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

در صورتیكه c1 را بعنوان یك كد خطی (n1,k1) و c2 را بعنوان یك كد خطی (n2,k2) در نظر بگیریم ، كد خطی  (n1n2,k1k1)  به شكل یك آرایه مستطیلی از n1 ستون  و n2 سطر كه  هر ردیف آن یك بردار كد c1  و هر ستون آن یك بردار كد c2 خواهد بود در می آید .

شكل 8 – كد آرایه ای برای كد محصول C1*C2

این كد آرایه ای ، محصول مستقیم یا كد محصول c1 و c2 نامیده می شود . k1k2 دیجیت در گوشه سمت راست بالایی از آرایه ، سمبل های اطلاعات هستند . دیجیت ها در گوشه سمت راست بالایی از این آرایه از قانون پریتی چك برای c1  در ردیفها و دیجیت ها در گوشه سمت راست پائینی از قانون پریتی چك c2 در ستون ها قابل محاسبه هستند . اكنون دیجیت ها را در گوشه سمت چپ پائینی با استفاده از قانون پریتی چك برای c2 از ستون ها یا قانون پریتی چك از ردیف ها برای c1 محاسبه می كنیم . و در هر طریقه ، (n1,k1)*(n2,k2) دیجیت های چك كردنی خواهیم داشت . برای انكدینگ كد محصول ، ممكن است ابتدا k2 ردیفی را از آرایه اطلاعات بر پایه قانون پریتی چك برای c1 انكد كرده و سپس n2 حاصل از ستون ها را برای c2 انكد نمائیم . اگر c1 دارای حداقل وزن d1 و c2 دارای حداقل وزن d2 باشد ، حداقل وزن كد محصول d1d2 خواهد بود . یك بردار كد با حداقل وزن ، در كد محصول بصورت زیر شكل می یابد :

1-    انتخاب یك حداقل وزن برای بردار كد c1 و حداقل وزن برای بردار كد c2 .

2-                شكل دادن به صورت یك آرایه در تمام ستون های متناظر با صفرها در بردار كد از c1 كه« صفر » باشند و تمام ستونهای متناظر با «یك»  در بردار كد c1 كه حداقل وزن از كد c2 انتخاب گردد .

مشخص كردن پترن های قابل تصحیح برای كد محصول ساده نمی باشد و تصحیح خطاها ابتدا بر روی ردیف ها و سپس بر روی ستون ها انجام می پذیرد . و پترن هایی قابل تصحیح خواهند بود كه هم بصورت سطری و هم بصورت ستونی قابل تصحیح باشند . كد محصول توانایی تصحیح هر تركیبی از [(d1d2-1)/2] خطا را داراست . در صورتیكه l1 و l2 توانایی تصحیح خطای برست از كدهای c1 و c2 به ترتیب باشد ، توانایی تصحیح خطای برست از كد محصول c1 و c2 می تواند بصورت زیر آنالیز گردد :

یك آرایه كد فرستاده شده را در نظر  می گیریم كه بصورت ردیف به ردیف ارسال شده و سپس در خروجی كانال ، دیجیت های دریافت شد . دوباره به داخل یك آرایه بصورت ردیف به ردیف مرتب شده اند ، خطاهای برست با طول n1l2 یا كمتر بر روی بیشتر ردیف های متوالی مl2+1 اثر می گذارد . وقتی كه دیجیت های دریافت شده دوباره مرتب می شوند داخل یك آرایه ، هر ستون با طول l2  دارای برست خواهد شد . و نتیجتاً توانایی تصحیح خطای برست از كد محصول حداقل n1l2 خواهد بود . با ارنج مشابه ای می توان تصحیح خطای برست با طول n2l1 را انجام داد و در نتیجه بنا بر نوع ارنج كردن توانایی تصحیح خطای برست l از كد محصول حاصله دارای ماكزیمم {n1l2,n2l1} است . پس اگر یd2,d1 حىاقل فواصل كىهای c2,c1 به ترتیب باشند ، كد محصول c2,c1 توانایی تصحیح خطاهای رندم t=[(d1d2-1)/2)]  یا كمتر و بطور همزمان تصحیح خطای برست با طول l=max{n1t2,n2t1}  را دارا خواهد بود كه داریم : t1=[(d1-1)/2] , t2=[(d2-1)/2]  . در صورتیكه اجزاء كدهای c2,c1 چرخشی باشند و n2,n1 وابسته اولیه باشد ، كد محصول c1*c2 چرخشی خواهد بود .

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

اگر هر عنصر    در حوزه Galois ،    را درنظر بگیریم كه بصورت یك مجموع از   بشكل زیر باشد :  كه  یك عنصر اولیه از  باشد و0  یا a=1  پس بین  و  تناظر یك به یك وجود خواهد داشت . پس m تایی  را می توان m بایت نمایش دهنده از  نامید . در یك كد Reed-Solomon  با تصحیح خطای t با سمبل كد از  ، اگر هر سمبل با m بایت متناظر آن نشان داده شود ، یك كد خطی باینری با پارامترهای زیر خواهیم داشت  : n-k=2mt  و  . این كد توانایی تصحیح هر پترن خطا كد بر t یا كمتر m بایت تاثیر می گذارد ، را داراست . مهم نیست كه یك بایت دارای خطا یا تمام m بیت دارای خطا باشند ، آن یك بایت خطا تلقی می شود . در خروجی كانال ، بردار باینری دریافت شده بر بایت تقسیم می شود . هر بایت به داخل یك سمبل  منتقل می شود . پس اگر یك پترن خطا بر t تاثیر گذارد یا بر بایتهای كمتری در یك كد
 Reed-Solomon  ، واضح است كه پترن خطا می تواند بوسیله روش دیكدینگ تشریح شده در قبل ، تصحیح گردد . این كد باینری را یك كد تصحیح خطای t بایت می نامند . و در واقع این كد یك كد تصحیح خطای برست فاز بندی شده چند تایی است .

كدهای باینری درایو شده از كدهای  Reed-Solomon   بیشتر در برابر خطاهای دسته ای یا برست نسبت به خطاهای رندم موثرند .  بعنوان مثال درصورتیكه یك برست با طول 3m+1 نتواند بر بیشتر از 4 بایت موثر باشد . یك كد تصحیح كننده 4 بایت هر برست تكی با طول 3m+1 یا كمتر را تصحیح كند . همچنین می تواند بطور همزمان هر تركیبی از دو برست با طول m+1 یا كمتر را تصحیح كند زیرا هر برست نمی تواند بر بیش از 2 بایت موثر باشد . در حالت نرمال هر كد Reed-Solomon  

باینری تصحیح كننده خطای t  بایت توانایی تصحیح هر تركیبی از  یا كمتر  برست با طول l و یا تصحیح هر برست تكی با طول (t-1)m+1  یا كمتر را داراست . همچنین همزمان هر تركیبی از t یا كمتر خطای رندم را تصحیح می كند .

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

الحاق یا بهم پیوستن ، روش خاصی ازساخت كدهای طولانی از كدهای كوتاه تر است و این ساختار بعنوان روش ساده ای در مواردی ( مثلاً تجهیزات ) كه احتیاج به كدهای طولانی دارند ، بكار می رود .

یك كد بهم پیوسته ساده از تركیب دو كد بدست می آید . یك كد باینری c1(n1,k1) و یك كد غیر باینری c2(n2,k2) با سمبل هایی از  . سمبل هایی از c2 با بایتهای متناظرشان از سمبل باینری k1 نشان داده می شوند . بطور معمول یك كد Reed-Solomon  برای c2 بكار می رود . انكدینگ شامل 2 مرحله است كه در شكل 9 نشان داده شده است :

شكل 9 – سیستم ارتباطات بكار رفته برای یك كد بهم پیوسته

اول  k1k2 بایت دیجیت اطلاعات باینری به k2 بایت از k1 دیجیت اطلاعات تقسیم می گردد . این k2 بایت مطابق قانون c2 از یك بردار n2 بایتی ، انكد می گردد .

سپس هر k1 دیجیت بایت ، در یك بردار كد در c1 انكد می گردد كه پاسخ آن در یك رشته از n2  بردار كد از c1 است و مجموع n1n2 دیجیت منتقل می گردد .

ابتدا بردار كد c1 در یك زمان و در یك ردیف متوالی و سپس برآیند كه یك كد خطی باینری (n1n2,k1k2) است منتقل می گردند . اجزاء كدهای c1 و c2  به ترتیب كدهای درونی و بیرونی نامیده می شوند . اگر حداقل فواصل آنها را به ترتیب d1 و d2 در نظر بگیریم حداقل فاصله كد بهم پیوسته d1d2 خواهد شد . همچنین دیكدینگ این كد نیز در دو مرحله انجام می پذیرد .

ابتدا دیكدینگ برای هر بردار كد c1 دریافت شده ، انجام می پذیرد و دیجیت های چك شده حذف می گردد .

و با قیمانده آن یك ترتیب از n2k1 بایت دیجیت خواهد بود . این بایت ها همچنین مطابق همین روش برای c2  دیكد می گردند و انتها پیغام تصحیح شده نهایی بدست می آید .

 برای اجرای دیكدینگ یك تركیب مستقیم از اجرای آن برای كدهای c1 و c2 و استفاده از تجهیزات سخت افزاری نیاز است . كدهای بهم پیوسته بر تركیبی از خطاهی رندم و برست موثراند و پترن بایت ها غیر قابل تصحیح بوسیله c1 باید از پترن خطای قابل تصحیح برای c2 اگر كدهای بهم پیوسته پترن خطا را تصحیح كند ، استفاده كند و خطاهای رندم پراكنده شده بوسیله c1 تصحیح می گردند .

برست در این حالت ممكن است بر تعداد كمی از بایت ها اثر گذار باشد ، اما احتمال بد این است كه c2 نتواند آنها را تصحیح كند كه این بایتها بوسیله c2 تصحیح خواهد شد .

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

در صورتیكه  یك عنصر با مرتبه n   در حوزه Galois ،    باشد ، n  یك فاكتور از  خواهد بود .  را چند جمله ای كمین از    با پریود n در نظر می گیریم . درجه  ، m0  برابر m یا فاكتوری از m خواهد بود . فاكتور پیشنهادی مانند b را برای  nدر نظر می گیریم   بطوریكه  باشد و n=ab . سپس خواهیم داشت :   . مادامیكه مرتبه ، n  باشد و b

 را یك چند جمله ای مولد كد چرخشی C2 با طول n  در نظر می گیریم كه توانایی تصحیح t خطای رندم یا كمتر را دارا باشد ، روشن است كه  فاكتوری از  است . اگر g(x) كوچكترین مضرب مشترك از  باشد و{ g(x)=LCM{ روشن است كه g(x) قابل تقسیم بر  خواهد بود و می توان آنرا به شكل  نشان داد .g0(x) فاكتوری اؤ  خواهد بود . اكنون ما یك كد چرخشی c با طول n تولید شده توسط g(x) خواهیم داشت . این كد c یك زیر كد از هر دو كد آتشی c1 تولید شده توسط  و یك  c2 تصحیح كننده خطای t  تولید شده توسط g2(x)  خواهد بود .

چون c یك زیر كد از كد آتشی c1  است ، c توانایی تصحیح هر خطای برست تكی با طول (b+1)/2  یا كمتر را داراست و چون c یك زیر كد از كد c2 است توانایی تصحیح هر تركیبی از t یا كمتر خطا را داراست . همچنین g(x) دارای فاكتور (X+1) است پس حداقل فاصله c ، 2t+2 خواهد بود .

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

كدهای كانولوشن جهت تصحیح خطای برست ابتدا توسط Hegelarger  مطرح گردید . این كدها شد . این كدها در حالت فازبندی شده نیز در ابتدا توسط Ash,Wyner بررسی گردید . از تكنیك در میان سازی می توان جهت تبدیل كدهای كانولوشن تصحیح كننده خطای برست استفاده كرد . همچنین 3 روش تصحیح خطاهای توام رندم و برست با استفاده از این كدها در این بخش بررسی می گردد.

- میزان توانایی تصحیح خطای برست :

اگر  را ترتیب خطا در یك BSC در نظر بگیریم می توان فرض كرد :

فرض1 : ترتیب خطای بیتها    را یك برست با طول b نامید كه وابسته  به فضای گارد با طول g است اگر :   

فرض2 : g بیت جلوتر از   و g  بیت بعد از   تماماً صفر باشد .

فرض 3 : b بیت از   در طول   شامل هیچ زیر ترتیبی از g های صفر نباشد.

بنابراین طول برست همیشه با فضای گارد وابستگی دارد . Gellager نشان داد كه برای هر كد كانولوشن با نرخ b كه تمام برست های با طول b یا كمتر وابسته به فضای گارد با طول g را تصحیح می كند : (17)   

حدود ( مرز ) رابطه 17 مرز تصحیح خطای برست بطور كامل است . Messey  نشان داد كه اگر اجازه دهیم كه یك بخش كوچكی از برستبا طول b  بطور ناصحیح دیكد گردد ، فضای گارد می تواند كاهش یابد .

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

در این بخش دو كلاس از كدهای كانولوشن تصحیح خطای برست معرفی می گردند كه عبارتند از كدهای
 Berlekamp – Preparata و Iwadre-Messey  .

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

یك كد كانولوشن (n,n-1,m) سیستماتیك جهت تصحیح یك بلوك تكی در یك فضای محافظت شده ( گارد ) شامل m  بلوك خطای آزاد ( یعنی یك برست می تواند بر بیش از یك بلوك با طول اجباری تاثیر بگذارد ) در نظر می گیریم . كه این كد دارای توانایی تصحیح خطای برست فاز بندی شده از یك بلوك وابسته فضای گارد از m بلوك را دارا باشد . برای طراحی این چنین كدی با اطمینان حاصل كنیم كه هر ترتیب خطای   در یك سیندرم   پاسخ می دهد . این روشن می سازد كه هر ترتیب خطا با  باید حاصل آن یك سیندرم متمایز باشد و هركدام از سیندرم ها باید متمایز باشد .

براین اساس ، اولین بلوك خطای   می تواند با دیكد كردن تصحیح شود . اگر اولین طول اجباری آن شامل حداقل یك بلوك غیر صفر باشد ، هر بلوك خطای متوالی میتواند دیكد شود . یك كد كانولوشن (n,n-1,m)  بوسیله مجموعه ای از
چندجمله ایهای مولد  تعریف می شود . سیندرم را می توان بصورت زیر نوشت :

  (18)   كه ماتریس پریتی چك با ماتریس شیفت T می باشد . برای یك كد تصحیح خطای برست بهینه ،  بصورت زیر در می آید :  (19)

 را طوری باید انتخاب كرد كه شرایط تصحیح خطای برست را محیا كند . در مجموع برای هر   ، شرط   باید برای تمام  محقق گردد .

این شرط را می توان به این صورت  نیز نوشت:     (20)

این ساختار می تواند از این كدها برای تولید كدهای تصحیح خطای برست فازبندی شده بهینه برای k

مدارات انكدینگ و دیكدینگ این كدها در مرجع [1]  تشریح شده اند .

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

این كدها ، كلاس موثر دیگری  از كدهای كانولوشن برای تصحیح خطای برست با طول b نسبت به فضای گارد g هستند .
برای هر كد كانولوشن تصحیح خطای برست (n,n-1,m) با پارامترهای زیر مشخص می گردد :

   كه  یك عدد صحیح است و چند جمله مولد بصورت زیر بدست می آید :   كه   مراحل انكدینگ و دیكدینگ با این كد در مرجع [1] تشریح شده است .

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

از این تكنیك جهت مشخص كردن كدهای تصحیح خطای برست طولانی كدهای كانولوشن مانند كدهای بلوكی می توان استفاده كرد . این تكنیك با مالتی پلكس كردن خروجی   انكدر جداگانه با طول های متمایز  از انتقال در كانال كد بسادگی امكان پذیر است . بیت دریافت شده سپس دی مالتی پلكس شده و به دیكدرهای جداگانه  فرستاده می شوند یك برست با طول  در كانال سپس مانند یك خطای تكی در هر دیكدر جداگانه است . از این رو اگر هر دیكدر توانایی تصحیح خطاهای تكی با طولهای متفاوت را داشته باشد با  یك در میان سازی ، تمام برست های با طول  یا كمتر نسبت به فضای گارد

با طول  تصحیح خواهد شد .

در عمل به استفاده از  انكدر جداگانه احتیاج نمی باشد اما فقط بكار بردن یك انكدر و یك دیكدر به همان طریقه ، عملكرد معادل  انكدر و دیكدر را داشته باشد ، كفایت می كند .

یك سیستم كدینگ كانولوشن (n,k,m) با درجه یك درمیان سازی   در شكل 10 نشان داده شده است . در این شكل فرض شده است كه  ضریبی از n است و interleaver  بین انكد و مالتی پلكسر قرار دارد . و n بیت انكد شده را در بلوك با  حائل شده ، جدا می كند .

در مجموع انكدر با جایگزینی هر واهد تاخیر با یك رشته از واحد تاخیر تغییر می یابد . و از این رو یك انكدر معادل  انكدر جداگانه n بیتی خواهیم داشت .

 interleaver در شكل 10 به    واحد تاخیر احتیاج دارد .  در عمل با فرض دیكدر استاندارد ، k رجیستر m   بیتی برای دوباره انكد كردن و (n-k)m بیت رجیستر سیندرم و  واحد تاخیر احتیاج است . از این رو مجموع حافظه مورد نیاز در دیكدر فوق برابر است با :  .

شكل  10- یك سیستم كدینگ كانولوشن (n,k,m) با درجه یك درمیان سازی

-كدهای كانولوشن تصحیح كننده خطای برست و رندم

2-7-كدهای كانولوشن تصحیح كننده هردو خطاهای برست و رندم :     Burst – And-Random –Error-Correcting- Convolutional  Codes

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

یك در میان سازی یك كد  با توانایی t تصحیح خطای رندم از درجه  در یك سیستم كه گروههای تصحیح از t یا كمتر برست با طول  یا كمتر را داراست قابل اجرا می باشد.

این تصحیح خطای برست چند گانه نامیده می شود . بعضی از برست ها در گروههای جداگانه ممكن است شامل خطاهای پراكنده باشند . چند نوع از این كدها در زیر تشریح شده است .

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

كد كانولوشن سیستماتیك (2,1,m)   با  ,  كه  یك عدد صحیح است را در نظر می گیریم . سیندرم را بصورت    تعریف می كنیم .

چهار مجموع متعامد خواهیم داشت . [1] از این رو اگر دو یا كمتر خطا از بین چندجمله ای های متعامد وجود داشته باشد ، می تواند توسط یك دیكدر لاجیك بیشین حذف گردد .

همچنین با این كد هر  یا كمتر خطای رندم با فضای گارد  تصحیح می گردد . بلوك دیاگرام انكدر / دیكدر در شكل 11 نشان داده شده است . توجه شود كه برای  بزرگ g/b = 3 می گردد و این برای R=1/2 بهینه است .و مرز Gallager را ارضا می كند .

شكل 11 – بلوك دیاگرام سیستم كاملی از یك كد -   diffuse برای تصحیح دو خطای با نرخ R=1/2

از این رو دیكدینگ دارای فیدبك با توانایی تصحیح خطای مشابه برای تمام بیت های خطای اطلاعات بدست می آید . انتشار خطا از ویژگیهای مدهای منتشرشونده است . نمونه هایی از این كدها در جدول 2 آمده است :

جدول 2 – كدهای متعامد تصحیح خطای ، -diffuse با R=1/2

Orthogonalization rules			m
…	....	2 ....	.....	2 ....

* : جدول كامل در مرجع [1]

تصحیح خطاها توسط كدهای خود متعامد در اجرا ساده تر  هستند . لیستی از این كدها در جدول 3 آمده است . نسبت g/b این كدها بزرگتر از مرز Gallager است و بهینه می باشند ولی حساسیت كمتری به  انتشار خطا دارند .

جدول3 – كدهای خود متعامد تصحیح كننده خطای برست -  ، -diffuse

(a)R=1/2 codes

		m
....	1 ....	.....	1 ....

(b)R=2/3 codes

			m
....		3 ....	.....	2 ....

... * : جدول كامل در مرجع [1]

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

كد كانولوشن سیستماتیك (2,1,L+M+5)   با  در نظر بگیرید . بطور عمومی سیستم جستجوی برست Gallager تمام برست های باطول b=2(L-5) یا كمتر را با یك فضای گارد
g=2(L+M+2) با  یا كمتر خطای رندم تصحیح می كند . انكدر برای كد فوق در شكل 12 نشان داده شده است.

اولین 5 واحد تاخیر در انكدر با مجموع های چك ، جهت تصحیح 2 خطای رندم یا كمتر با طول های متفاوت بكار می رود . این سیستم تنها پترن های خطا   یا كمتر خطاهای رندم كه  باشد را تصحیح می كند .

شكل 12- مدار انكدینگ برای كدهای جستجوی خطای برست Gallager با R=1/2

مدار دیكدینگ برای كد فوق در شكل 13 نشان داده شده است .

شكل13- مدار دیكدینگ برای كدهای جستجوی خطای برست Gallager با R=1/2

 عملكرد این مدار در مرجع [1] تشریح شده است . با توجه شود كه تخمین پذیرش برای هر بیت خطای برست برابر است با :

Pr[برست آشكار نشده ]=

برای اینكه این تخمین تصحیح گردد باید طول برست از L-5 بلوك یا b=2(L-5)  بیت تجاوز نكند . در سایر موارد بیت های خطا از یرست باید تحت تاثیر دیكدینگ این فضای گارد بیت های خطا باشد . نسبت g/b برای این حالت تقریباً 1 است .

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

سیستم تله گذاری برست Tong شبیه سیستم جستجوی  شبیه سیستم جستجوی برست Gallager است مگر اینكه این سیستم بر پایه كدهای بلوكی بیشتر از كدهای كانولوشن اما با وجود حافظه میل دارد .

یك كد بلوكی سیستماتیك (n=3m,k=2m) با R=2/3 در نظر بگیرید كه توانایی تصحیح خطای t داشته باشد . انكدر برپایه این كد در شكل 14 آمده است . در مجموع برای عملكرد این انكدر كافیست بلوك حافظه را به سیستم
تله گذاری برست كه قبلاً بیان شده بود ، اضافه نماییم .

پس كد بلوكی به یك كد كانولوشن (n=3m,k=2m,m=2L) تبدیل می گردد .

شكل 14 – مدار انكدینگ برای كد تله گذاری برست Tong با  R=2/3

دیكدر برای این سیستم در شكل 15 نشان داده شده است . عملكرد این مدار نیز بطور كامل در مرجع [1] تشریح شده است .

شكل 15 – مدار دیكدینگ برای كد تله گذاری برست Tong با  R=2/3

سیستم تله گذاری برست تشریح شده در فوق تمام برست های تاثیر گذار بر L بلوك دریافت شده را تصحیح می كند . از این رو b=(m-1)L+1   است و فضای گارد باید حداقل شامل 2L بلوك با خطای آزاد متوالی دارای برست باشد . پس : g=2nL+(n-1)  و برای  L,n بزرگ خواهیم داشت :  g/b=2 . كه مرز فوقانی برای تصحیح تمام خطاهای برست با نرخ R=2/3 را ارضا می كند . سیستم تله گذاری فوق با كمی تغییر به سادگی برای هر نرخ  می توان بكار برد .

شكل 16 - مدار انكدینگ برای كدهای جستجوی خطای برست Gallager با R=1/2

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

Low Delay Burst Erasur Correction Codes [2]

3-1-مقدمه :

در شبكه های مختلف از بین رفتن بسته ها بصورت Burst رخ می دهد . كاربردهای قراردادی برای تصحیح خطا و بازیابی بسته ها  اغلب به یك درمیان سازی (Interleaving) بین كدهای اصلی و دیكدینگ های طولانی با تاخیر زیاد می انجامد . این تاخیر های طولانی در ارتباطات مالتی مدیا ( چند رسانه ای ) زمان واقعی (Real Time) در كاربردهایی از قبیل صدا روی IP ، (VOIP) مورد پذیرش نمی باشد . در نتیجه كدهای تصحیح پاك شدگی با تأخیر محدود شده ، تشریح می گردند .

همانگونه كه در فصل 1 بیان گردید پروتوكل های زیادی برای شبكه های سوئیچ كننده وجود دارد . بعلت تاخیر زیاد در كاربردهای Real-Time‌ ، در استفاده از ARQ  ، FEC و نیز تكنیك یك درمیان سازی محدودیت وجود دارد . بر اثر تراكم در لینك ها ، از بین رفتن بسته رخ می دهد (Loos)   . راه های گوناگونی جهت اضافه كردن افزونگی برای بازكردن بسته های از دست رفته وجود دارد كه از بین آنها ، راه مفید باید شامل خصوصیات زمان واقعی تحت بسته های شبكه باشد . بعضی از انواع كدهای كانولوشن كوتاه شده جهت تصحیح خطای برست در فصل قبل معرفی شده است .

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

مطابق استاندارد ما یك نرخ  R=k/n را برای تركیب انكدر ودیكدر درنظر می گیریم . انكدر یك سیستم زمان گسسته علی است . كه در مرحله i  ، k سمبل  بعنوان ورودی و n  سمبل  بعنوان خروجی   می گیرد . در این نوشته  ، نشاندهنده j امین سمبل ورودی در زمان i ، وقتی  j امین سمبل خروجی در زمان  i باشد ، است . دیكدر بطور متناظر ترتیبی از  n سمبل    بعنوان ورودی می گیرد و سعی می كند ترتیب  را بازیابی كند . اگر دیكدر  را از و  و ... بازیابی كند ، می گوییم كه دیكدر بصورت دیكدینگ با تاخیر  T  عمل می كند .  یك فرستنده دارای یك رشته اطلاعات   است كه به انتقال با استفاده از n  سمبل در هر بسته احتیاج دارد .

برای ساختن اتاقی برای افزونگی (redundancy) ، اطلاعات اصلی به  k

برای تشریح مساله یك كد با نرخ R=1/2 ، و بسته ای كه 2n‌ بیت اطلاعات را حمل می كند در نظر می گیریم . اگر هر بخش از اطلاعات در یك بسته با اندازه 2n حمل گردد ، هیچ راهی برای بازیابی اطلاعات وجود نخواهد داشت . نتیجتاً ما به افزودن افزودگی احتیاج داریم . بنابراین پس از فشردگی بیتهای اطلاعات از 2n به n  بیت در هر بسته ، افزونگی را در اولین n بیت از اطلاعات ، اضافه می كنیم . ( در واقع حجم اطلاعات زیاد نمی شود ) دومین n بیت اطلاعات در بسته كد شده می تواند برای ذخیره اطلاعات اضافی از قبیل بیت های پریتی چك ، مجموع های چك كننده ، كپی هایی از افزوده و غیره بكار رود . لازم به یادآوری است كه i امین بسته انكد شده بعنوان  است .

شكل 1-2 یك مثال ساده از شمای انكدینگ را كه بسته  i  شامل اطلاعات اصلی و  مانند  ( یك كپی از 3 بسته قبل )‌ است ، نشان می دهد . این شمای انكدینگ می تواند یك برست با 3 بسته از دست رفته یا كمتر را با دیكدینگی با تاخیر 3 ، تصحیح كند . برای نشان دادن این موضوع فرض كنید كه  و  و گم شده اند ( از دست رفته اند ) وقتی بسته  دریافت می گردد ، هر دوی  و  بازیابی می گردد . مادامیكه  دریافت گردید ، 3 بسته بعد از آن نیز ارسال می گردد  بطور مشابه وقتی و  دریافت گردید  و  بازیابی می شوند . ( با تاخیر دیكدینگ برابر 3 )

شكل1-2 :  یك مثال از شمای انكدینگ .

 بسته i شامل دیتای اصلی ،  یك كپی از افزونگی و  از 3 بسته قبل در نظر گرته شده است . اگر بسته های و   مفقود شوند ، دیتا می تواند از بخش افزونگی بعدی بازیابی شوند .

- مرز یا محدوده دیكدینگ با تاخیر حالت فوق :

شمای كدینگ ساده شكل 1-2 ، ایده اضافه كردن افزونگی را در شكلی از اختلاف زمانی ( دایورسیتی زمانی ) نشان می دهد . در تئوری اطلاعات كدهای مكمل زیادی وجود دارد كه بهتر از تكرار جهت بازیابی بسته های از بین رفته جواب می دهند .

تئوری 1 : اگر نرخ كد R  بتواند تمام برست های پاك شده با طول s‌را با دیكدینگ با تاخیر T  تصحیح كند ، سپس مرز زیر را  خواهیم داشت :  

  در واقع این مرز دیكدینگ با تاخیر شبیه مرز بیان شده بعنوان مرز فضای گارد می باشد. لازم به یادآوری است كه مرز فضای گارد كه یك كد با نرخ R بتواند تمام برست های با طول s و پاك شدگی g سمبل را  تصحیح كند ، برتبر است با :  و T/s باید حداقل 1 باشد تا g/s بتواند كمتر از 1 ( حالت بهینه )‌برسد .

مورد دیگر استفاده از كدهای Read-Solomon  می باشد كه كدهای از این نوع كه تاكنون تشریح شده اند ، مرز فضای گارد را ارضا كرده اما مرز تاخیر را ارضا نمی كنند . در فصل آتی الگوریتم خاصی برای این كدها طراحی گردیده است تا تاخیر دیكدینگ را نیز ارضا كند .اگر k   سمبل انكد شده با یك كد Read-Solomon (n,k)  ، در نظر بگیریم با این نرخ R=k/n می توان هر n-k پاك شدگی را در یك برست بازیابی كند . مرز تاخیر ابزار عملی در طراحی سیستم می باشد .

-مثال

بعنوان مثال لینكی را در نظر می گیریم كه با نرخ 64kb/s بسته های 10ms‌را ارسال می دارد و برست های با  بسته گم شده را باز یابی می كند . برای اینكه حداكثر تاخیر 120ms با T=12 بسته برای این سیستم قابل تحمل  باشد ، باید  باشد . و با بكاربردن یك كد تصحیح كننده برست مناسب ، میزان ¾*64kb/s=48kb/s  از صوت جهت انكد كردن در دسترس خواهد بود .

برای ساختن یك كد با نرخ 2/3 افزونگی بصورت كپی از اطلاعات طولانی نمی توان در نظر گرفت . راه عملی ، استفاده از پریتی چك برای ساختن كد  با نرخ 2/3 است و می توان قانون انكدینگی بصورت زیر در نظر گرفت :   (2-2)  . شكل 2-2 ، بازیابی یك برست با 1 بسته از بین رفته و دیكدینگ تاخیر 2 نشان می دهد . بعنوان مثال بسته گم شده  را در نظر می گیریم . برای بازیابی از دیكدر منتظر می ماند تا   را دریافت كند و بازیابی  با استفاده از   انجام می گیرد .

شكل 2-2 : دیكدینگ یك بسته از بین رفته با استفاده از كد پریتی چك .

با استفاده از تكنیك یك در میان سازی با درجه  می توانیم حالت فوق را تعمیم داده و یك كد تصحیح برست را به كد تصحیح برست  با دیكدینگ با تاخیر  بدست آوریم . شكل 2-3 مثالی از این كد یك در میان شده با نرخ R=2/3 ‌ و  را كه می تواند یك برست با 2 بسته از دست رفته و زمان تاخیر T=4‌ را بازیابی كند ، نشان می دهد . 

شكل3-2 : دیكدینگ یك برست با 2 بسته از بین رفته با استفاده از تكنیك یك درمیان سازی

با استفاده از كدهای پریتی چك تكی به همین طریقه می توان كدهای با نرخ k/(k+1) بسازیم كه برست های با  پاك شدگی و تاخیر  را بازیابی كند . قانون انكدینگ برای این چنین كدی بصورت زیر در می آید :

  (3-2) . بنابراین كه این كدها بهترین حالت برای تصحیح برست با نرخ k/(k+1) و تاخیر دیكدینگ  است .

-  بهینه سازی :

كدهای سیستماتیك خطی Read-Solomon  ‌ را می توان برای بازیابی كدهای (n,k,d=n-k+1) با استفاده از سمبل های q آرایه ای تحت  كه  باشد ، استفاده كرد .

قانون دیكدینگ زیر را می توان استفاده كرد :

 (4-2)  شكل 4 پراسس انكدینگ و دیكدینگ را برای  برای برست با پاك شدگی 2 نشان می دهد . درصورتیكه سمبل های كد شده  پاك شده باشد ، دیكدر منتظر می ماند تا  را دریافت كند . سپس از الگوریتم دیكدینگ برای  جهت بازیابی  از   استفاده می كند . اگر  دارای حداقل فاصله 3 بوده و هیچكدام از پاك نشده باشد ،  با موفقیت بازیابی خواهد شد . 

در ادامه دیكدر  را دریافت می كند و با استفاده از  ، دیكد  انجام می پذیرد . اگر در مرحله قبل بازیابی شده باشد و  در مرحله قبل پاك نشده باشد ،   با موفقیت بازیابی خواهد شد . و بالاخره درصورتیكه  را دریافت كرده باشد ،  اگر  پاك نشده باشند ، با موفقیت بازیابی می شود .

در مجموع با توجه به شكل 4-2 مشاهده می گردد كه برای یك برست با پاك شدگی 2 كه در زمان t شروع شده است ، برای اجرای قانون دیكدینگ فوق بایستی سمبل های t-1,t+3,t+2 پاك نشده باشند . پس تاخیر دیكدینگ برابر T=3  خواهد بود كه تاخیر دیكدینگ بیان شده در بخش قبل را ارضا می كند . لازم به تصریح است كه با بكار بردن كدهای با نرخ k/(k+1) و بكاربردن تكنیك یك درمیان سازی می توانیم  با  برای كدی با نرخ 3/5  بسازیم كه تمام برست های  و  را تصحیح می كند .

شكل 4-2 : كد  با نرخ 3/5 ، كه می تواند یك برست با پاك شدگی 2  را با دیكدری با تاخیر 3 تصحیح كند .

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

در مجموع با كدهای  دارای نرخ R=(ms+1)/(ms+1+s) (m,s اعداد صحیح غیر منفی ) ، می تواند برست های با s پاك شدگی با تاخیر دیكدینگ ms+1 را تصحیح نمود . و برای تعمیم آن با بكار بردن تكنیك یك درمیان سازی با پریود  ، این كدها برستهایی با  پاك شدگس و تاخیر دیكدینگ  را تصحیح می كنند . این كدها را با عنوان كدهای حداكثر كوتاه شده خواهیم شناخت . زیرا این كدها ، كوتاه ترین تاخیر دیكدینگ را نسبت به نرخ و توانایی تصحیح برست ها دارا خواهند بود .

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

با وجود مزایای كدهای تشریح شده فوق ، این كدها بیت های قابل دسترس برای كدینگ منبع را كاهش می دهند . درصورتیكه كانال با پاك شدگی بالا قابلیت تصحیح بصورت فوق را دارا باشد ،  كاهش نرخ كدینگ منبع تا حدودی جبران خواهد شد . نمودار فرضی از رفتار كدینگ كانال  در ازای ازبین رفتن بسته ها در شكا 5-2 آمده است . برای كانال بدون كدینگ حداكثر كیفیت سیگنال در گیرنده بدست می آید و تمام ظرفیت كانال به كدینگ منبع اختصاص می یابد ،  اما در این حالت از دست رفتن بسته ها نیز به حداكثر خواهد رسید . با بكاربردن كدینگ كانالی با نرخ 3/4 ، درصورتیكه هیچ بسته ای از دست نرفته باشد ، سرعت انتقال كاهش می یابد . اما اگر بسته های از دست رفته داشته باشیم ( در حالت عمومی )‌ ، این كد كیفیت سیگنال بهتری را همراه با تصحیح بسته های از دست رفته حاصل می كند . كد با نرخ 1/2  بسته های از بین رفته بیشتری را با كیفیت پائین تر ، تصحیح خواهد نمود .

شكل 5-2 : نمودار تصوری از كیفیت سیگنال برای سطوح مختلفی از كدینگ كانال كه بصورت تابعی از نرخ از دست رفتن بسته‌ها ترسیم شده است .

ارسال با یك منبع گوسین در كانال Gilbert-Elliot و به روش تحلیلی با نمودار ترسیم شده در شكل 5-2 قابل توجیه است .

در كانال Gilbert-Elliot  پاك شدگی بسته ها در بدترین حالت (state1) رخ می دهد . و هرگز در حالت خوب (state 0 )  رخ نخواهد داد . انتقال از حالت خوب به بد و بالعكس به تر تیب با احتمالات αوβ رخ می دهد . (شكل 6-2) پس وقتی 1-β بزرگتر از α باشد ، كانال bursty است . مقادیر بزرگتر β متناظر با سطوح بزرگتر كانال bursty است . (شكل 7-2)

شكل6-2 : در كانال Gilbert-Elliot   (GEEC) بسته های گم شده همیشه در حالت بد رخ می دهد . (state1) و هرگز در حالت خوب (state0) رخ نخواهد داد .

شكل7-2 : دیاگرامی از كانال كه در آن بسته ها از دست می روند . بسته های از بین رفته ، تنها در حالت بد رخ می دهند . هر زمان كه بسته ای منتقل شده و به درستی دریافت گردد ، كانال رشته ای با از بین رفتگی β  احتمال α را تحمل می كند .

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

Read-Solomon(RS)

خلاصه :

 همانگونه كه در بخش های 1و2 ذكر گردید از كدهای RS‌ می توان جهت تصحیح پاك شدگی برست استفاده كرد . همچنین با استفاده از تكنیك یك درمیان سازی می توان از این كدها درپاك شدگی های بیشتر بهره برد . در فصل 2 تصریح گردید كه كدهای RS فضای گارد را ارضا كرده اما مرز تاخیر را برآورده نمی كند لذا در این فصل الگوریتمی طراحی شده است كه دیكدینگ این كدها را سرعت بخشیده و سبب ارضای مرز تاخیر دیكدینگ این كدها می شود . نتیجتاً این كدها را می توان بطور بهینه برای تصحیح پاك شدگی برست استفاده نمود . جهت تصحیح برست های با طول بالاتر در فصول بعد روشهای جدید تكنیك یك درمیان سازی و كاهش میزان افزونگی بیان شده است .

4-1- مقدمه : دو مزیت عمده این كدها عبارتند از : تصحیح هر دوی خطاهای رندم و برست و همچنین وجود الگوریتم های مناسب جهت دیكدینگ این كدها . از  اولین دیكدینگ های مناسب برای این كدها ، Brelekamp-Messey  بود كه در فصل 1 تشریح گردید . الگوریتم Brelekamp-Messey   ابتدا سیندرم ها را می یابد و سپس موقعیت خطاها را بر حسب اهمیت آنها جستجو می كند . الگوریتم مطرح شده در این بخش شبیه الگوریتم Brelekamp-Messey   است با این تفاوت كه پیغام  سمبل ها  بطور مستقیم بدون یافتن موقعیت خطاها و درنظر گرفتن اهمیت آنها ، محاسبه می گردد .

چند جمله ای پیغام در پراسس دیكدینگ قابل دستیابی است . عملكرد اصلی این روش در درون یابی و تقسیم چند جمله ایها همراه با الگوریتم محاسباتی سریع  برپایه FFT انجام می پذیرد .

پارامترهای بكار رفته در این بخش عبارتند از :  q یك توان اولیه ،  یك میدان محدود از عناصر q و n,k,d اعداد صحیح با وضعیت :    هستند .

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

ما هر n عنصر از  را ثابت درنظر گرفته و می گوییم :  .برای انكد هر بسته از k سمبل اطلاعات كه هر سمبل  یك عنصر  است ، ابتدا چندجمله ای پیغام را بصورت زیر شكل می دهیم :

(3-1)  سپس محاسبه می كنیم (3-2)  

و كلمه كد متناظر با آن    بدست می آید .

بدین ترتیب وقتی سمبل های اطلاعات  تمام مقادیر را در  می گیرد ، ما  كلمه كد با طول n خواهیم داشت .

بطور واضح مشاهده می گردد كه این كلمات كد ، تشكیل یك كد خطی تحت  با حداقل فاصله d=n-k+1  را می دهد (كه بهترین حالت برای هر كد خطی (n,k) می باشد . ) و این كد ، كد Read-Solomon (n,k,d) نامیده می شود .

انكدینگ رابطه (3-2)  اصلی ترین بخش تحقیق Read-Solomon   است . و بعلت سیستماتیك نبودن مستقیماً در یك بخش از كلمه كد ظاهر نمی گردد . ادامه Gorenstein , Zierler كشف كردند كه این كد ها در حالت (n=q-1) بصورت كدهای چرخشی در می آیند كه می توانند چند جمله ایهای مولد را انكد كنند . رابطه (3-2) ، در واقع یك تبدیل فوریه گسسته (FFT) در حوزه محدود را بیان می دارد . و در ادامه الگوریتم دیكدینگ مطرح شده در واقع نوعی تبدیل عكس فوریه را ایجاد می نماید .

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

در صورتیكه  كلمه كد دریافت شده از كلمه كد c با t  خطا باشد كه  

بایستی چند جمله ای پیغام رابطه (3-1) را بگونه ای كه كلمه كد c را بیابد ، بدست آوریم . ابتدا چند جمله ای زیر را تشكیل می دهیم :   .   برای بسیاری از حالات قابل استفاده است ، برای مثال  وقتی n=q و  وقتی n|q-1 و   باشد . برای دیكد b به ترتیب زیر عمل می كنیم :

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

- ورودی : یك بردار دریافت شده :  

- خروجی : یك چند جمله ای پیغام   یا دیكدینگ خطا .

مراحل الگوریتم :

- مرحله اول ( درون یابی ) :  یافتن چند جمله ای واحد  از درجه  از قبیل :

- مرحله دوم  ( gcd جزئی ) گسترش الگوریتم به  مادامیكه g(x) دارای درجه <1/2(n+k)  گردد . فرض می كنیم كه در این زمان داریم :  .

- مرحله سوم (تقسیم طولانی ) : تقسیم g(x) بر v(x) :  كه deg r(x)

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

 الگوریتم بسط یافته وقتی دو چندجمله ای  تحت  موجود باشد را درنظر می گیریم . درصورتیكه :  باشد ، این الگوریتم یك تقسیم طولانی بصورت زیر شكل می دهد :   كه  و  .

و بطور همزمان محاسبه می كند : (3-3 )   . به آسانی اثبات می شود كه  و (3-4)  است .

 اصل موضوع 3-1 :اگر  دو چندجمله ای تحت  باشد ، سپس مطابق الگوریتم فوق الذكر :  . 

اثبات : از رابطه (3-1)‌می توان نوشت :   . با i  بار تكرار ماتریس فوق خواهیم داشت :  . كه داریم  .از این رو :  

   . اكنون ما از رابطه (3-4) می توانیم بنویسیم :   بنابراین :

وقتی  و i=m  باشد ، تئوری زیر از رابطه بالا حاصل می گردد .

اصل موضوع 3-2  : اگر با

  در نظر بگیریم می توان  را بصورت  فرض نمود . اگر در پایان      را داشته باشیم ، سپس  .

اثبات : الگوریتم فوق خارج قسمت ترتیب را برای هر دوی  و نیز  محاسبه می كند . فرض شود كه :

 كه  است .

درصورتیكه :  سپس خواهیم داشت :

 و  است و با توجه به اصل موصوع 3-1 خواهیم داشت :  (3-5)

اكنون تعریف می كنیم :  و خواهیم داشت :  .

و نیز داریم :

و درصورتیكه  باشد ، خواهیم داشت :

 و

 . با فرض بالا درجه  بطور مستقیم با درجه كاهش می یابد . این بدان معناست كه خارج قسمت ترتیبی از تا مرحله m  بالا می رود و نیز روشن می سازد كه ترتیبات  یكسان اند .

همچنین مرحله m‌ اولین زمانی است كه باقیمانده  دارای درجه  و دراین مرحله  خواهد شد كه  در رابطه 3-5 صدق می كند . اكنون به ادامه تصحیح الگوریتم برمی گردیم  .

تئوری3-3 : اگر بردار دریافت شده b دارای فاصله حداكثر (d-1)/2 از كلمه كد تعریف شده بوسیله چند جمله ای پیغام f(x) در رابطه 3-1 باشد ، سپس الگوریتم 1 ، f(x) را باز می گرداند و درسایر موارد ، الگوریتم خطا را باز می گرداند .

اثبات : فرض كنید كه بردار دریافت شده  دارای فاصله  از یك كلمه كد واحد  تعریف شده بوسیله f(x)  از روابط 1 و 2 باشد . چند جمله ای موقعیت یاب خطا را بصورت

 . درصورتیكه  كوفاكتوری از  در  باشد ، داریم :

  .   را بعنوان چند جمله ای واحد با    تعریف می كنیم ، از قبیل :  .

 سپس :   . در هر دو سمت ما دارای درجه كمتر از n كه دارای همان مقدار  وقتی در  برای  سنجیده می شود ، هستیم .

درصورتیكه  باشد . توجه می كنیم كه

  خواهد بود . سپس با توجه به تئوری 3-2 داریم :  . از این رو  این بدان معناست كه در مرحله 3 از الگوریتم 1 باقیمانده باید صفر و خارج قسمت  برابر f(x) گردد . بعبارت دیگر فرض كنید كه الگوریتم یك چند جمله ای  را در مرحله 3 بر می گرداند . روشن است كه  یك كلمه كد ( با درجه

  اما v(x) دارای درجه  خواهد بود . مشاهده می گردد كه  برای حداقل  مقدار i  . از این رو b بین فاصله (d-1)/2 از كلمه كد تعریف شده بوسیله رابطه  است . بنابراین b دارای فاصله ای بزرگتر از (d-1)/2 برای هر كلمه كد می باشد  و الگوریتم به حالت دیكدینگ خطا در مرحله 3 باز می گردد  . تئوری 3-3 نشان می دهد كه دیكدینگ خطای ممكن تنها هنگامی رخ می دهد كه خطاهای زیادی در انتقال كلمه كد اصلی در داخل دایره(محدوده) (d-1)/2 از هر كلمه كدی وارد شده باشد . در این حالت غیر ممكن است كه همه كلمات كد را آشكار كنیم .

توجه شود كه (3-6)  و (3-7) :  كه    چند جمله ای موقعیت یاب خطا است . چندجمله ایهای u(x) و v(x) در محاسبه شده در مرحله 2 ، در واقع  برای غیر صفر هستند . از این رو (3-8) :  خواهد شد . چند جمله ای و پیغام f(x) ، در  مخفی می شود . پنابراین با توجه به اصل موضوع 3-2 مشاهده گردید كه u(x) و v(x)‌ تنها از بخش فوقانی ضرایب  و  قابل محاسبه اند . در واقع چند جمله ایهای  (بخش های پائینی ) می توانند اختیاری باشد ، چون بر محاسبات u(x) و v(x)‌  تاثیری ندارند .

 از این رو برای ساده كردن می توانیم از ضرایب پائین صرفنظر كنیم . ما به درجه l از  احتیاج داریم كه :   كه  و l=n-d  خواهد بود . . در شروع مرحله 2 می توانیم بنویسم :

  كه  بخش های فوقانی ضرایب  هستند . برای مثال  وقتیكه  باشد. با اصل موصوع 3-2 می توانیم بطور مستقیم با استفاده از الگوریتم بسط یافته فوق u(x)  و v(x) را توسط  محاسبه كنیم . در اینجا  باید دارای حداكثر درجه  d-2 ( كه  d-1 بالاتر از ضرایب   ) است ، باشد و بعنوان سیندرم كلمه دریافت شده ،  آنرا ذخیره نماید . الگوریتم 1 را می توان بصورت زیر تغییر داد .

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

- ورودی : یك بردار دریافت شده :  

- خروجی : یك چند جمله ای پیغام   یا دیكدینگ خطا .

مراحل الگوریتم :

- مرحله اول ( درون یابی ) :  یافتن چند جمله ای واحد  از درجه  از قبیل :

- مرحله دوم  ( gcd جزئی ) از چندجمله ایهای  در روابط (3-9 ) و (3-10 )  به   می رسیم . و الگوریتم بسط یافته را برای   اجرا می كنیم . الگوریتم متوقف می شود مادامیكه g(x) دارای درجه <1/2(n+k)  گردد . فرض می كنیم كه در این زمان داریم :  .

- مرحله سوم (تقسیم  و ضرب كردن  ) : تقسیم  بر v(x) :  كه deg r(x)

با این الگوریتم تغییر یافته ، مرحله gcd ارزان تر خواهد شد ، اما آخرین مرحله گرانتر خواهد شد .  تئوری 3-3 فوق در این حالت نیز قابل اثبات می باشد .

- دیكدینگ با خطاها و پاك شدگی ها :

بسیار ساده است كه الگوریتم بیان شده را برای حالت دیكدینگ پاك شدگی ها اجرا كنیم . در عمل مطلوب است كه اطلاعاتی درمورد موقعیت خطاها جهت اجرای مدینگ داشته باشیم .

درصورتیكه  یك كلمه دریافت شده با s پاك شدگی باشد ، سپس t خطای بیشتر را می توان تصحیح نمود كه :  . S را بعنوان مجموعه موقعیتهای پاك شدگی ، ( كه این موقعیتها در واقع خطاهای آشكار شده اند ) و چند جمله ای پاك شدگی بصورت زیر در نظر می گیریم :  

اگر ما از موقعیت های موجود S در كلمات كد RS  ، صرفنظر كنیم سپس ما كلمه كد RS دیگری را با طول n-k و فاصله d=n-s-k+1 خواهیم داشت .

جهت دیكد b ما بطور ساده از موقعیت های موجود درS‌ صرفنظر كرده و با استفاده از الگوریتم 1 و 1a كلمه كد كوتاه شده را بدست می آوریم  . بطور دقیق تر ،  در الگوریتم های 1‌و 1a ما احتیاج داریم كه n را با n-s  ، d را با  d-s ،  را با  جایگزین كنیم و به مرحله درون یابی كه  با درجه  از قبیل  بر می گردیم . این عمل مادامیكه تمام كلمات برای كد كوتاه شده RS در برگرفته شود ، ادامه می یابد .

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

الگوریتم دیكدینگ تشریح شده به راه كار  موثری جهت ارزیابی ، درون یابی ، gcd ، ضرب و تقسیم احتیاج دارد . خوشبختانه تمامی این عملیات توسط تبدیل فوریه سریع (FFT)  قابل اجرا است و در این بخش این راه كار موثر را تشریح می كنیم .

برای تمام نقاط فیكس شده :  تبدیل از یك چند جمله ای به مقادیر  تبدیل فوریه گسسته DFT(f) نامیده می شود كه :  . سپس یك چندجمله ای

  با درجه  

از این رو  DFT یك زیر فضای  خواهد بود . درون یابی یك تبدیل معكوس است كه تبدیل فوریه گسسته معكوس  نامیده می شود و با  نشان داده می شود . باید توجه كرد كه منظور از تبدیل فوریه سریع  FFT هر الگوریتم سریعی است ، كه بتواند DFT با طول n و پیچیدگی   برای مقادیر كوچك  بدست آورد . با یك میدان محدود  ، ضرب و تقسیم كردن های چندجمله ایها از درجه

كار FFT اصولاً برای n  بزرگ انجام می پذیرد و ممكن است برای  nهای كوچك (n<1000) غیرضروری باشد . FFT می تواند دارای تاثیر بیشتری باشد ، اگر n محصولی از فاكتورهای كوچك و نقاط  با ساختار خاص باشد . بیشتر موارد مناسب با n با توانی از 2 یا 3 است . چند جمله  دارای n ریشه قابل تشخیص در یك میدان اساسی است.

- میدان محدود ساپورت كننده  FFT ضربی :

در این بخش خانواده ای از میدان های محدود  كه FFT های ضرب شونده را ساپورت می كند ، آورده شده است .

(a عناصر اولیه  برای هركدام از این p های اولیه ،  یك عنصر اولیه در  خواهد بود . هر كدام از این عناصر ، حدسی است كه  یك اولیه برای تمام i  باشد ، اما بطوركلی غلط خواهد بود مادامیكه این شناخته شود بعنوان تركیبی برای تمام  . در واقع عدد بعدی ،  و عامل بندی بعدی برای  برای تمام  شناخته می شود .

بطور رایج i=55 كوچكترین مقداری است كه از عدم مركب بودن  شناخته نشود . 

(b   . برای تمام مقادیر  كه مقدار اولیه را می گیرد ، عبارتند از :

 k = 1,2,5,6,8,12,18,30,36,41,66,189,210,209,276,353,408,438,534    

(c  . برای تمام مقادیر  كه مقدار اولیه را می گیرد ، عبارتند از :

 k = 1,3,13,15,25,39,55,75,85,127,1947

(d  . برای تمام مقادیر  كه مقدار اولیه را می گیرد ، عبارتند از :

 k = 2,4,6,14,20,26,26,50,52,92,120,174,180,190,290,320,390,432,616,830,1804

(e  . برای تمام مقادیر  كه مقدار اولیه را می گیرد ، عبارتند از :

 k = 1,2,3,6,7,11,14,17,33,42,43,63,65,67,81,134,162,206,211,366,663,782,1305,1411,1494

 (f تمام Mersenne های اولیه  . برای تمام مقادیر  كه مقدار اولیه را می گیرد ، عبارتند از : k=2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213,19937,21701,23209,44497,86243,110503,132049,216091,756839,859433,1257787,1398269,2976221,3021377,6972593

كه داریم :  كه قابل تقسیم بر  است . پس تنها یك FFT می تواند در   ظاهر گردد . مادامیكه  ،  ساده نشدنی در  خواهد بود و داریم : 

  . 

لازم به ذكر است كه این میدان  ، FFT های 4 تایی را نیز ساپورت می كند كه بسیار موثرتر از FFT های باینری هستند . برای تمام میدانهای فوق الذكر  ، می توانیم n را بعنوان توانی از 2  با n|(q-1) و  تمام ریشه های از  خواهد بود . سپس یك FFT و معكوس آن در این نقاط می تواند با استفاده از   در  عمل كند . در عمل این الگوریتم برای n<256 كارا است .

- FFT‌ وفقی :

متاسفانه FFT وفقی بسیاری از میدان های محدود را ساپورت نمی كند ، مخصوصاً میدانهایی كه از پارامترهای دو تایی كه معمولاً جهت كدهای تصحیح خطا بكار می روند ، تشكیل شده اند .

Cantor در سال 1989 راهی  برای استفاده از ساختار وفقی  میدانهای اساسی كشف كرد كه یك FFT‌ در میدان محدود با مرتبه   است . این FFT های وفقی برای p=2 از   جمع شونده و از     ضرب شونده در  استفاده می كنند .  برای میدانهایی كه از دو پارامتر و  استفاده می كنند Gao روش Cantor را بهبود بخشید.

وقتی m ، توانی از 2 باشد ، پیچیدگی زمانی فوق به  بهبود می یابد . همچنین برای یك  m ‌اختیاری ،  FFT‌وفقی از  جمع شونده و  ضرب شونده در  استفاده می كند . اینFFT  های وفقی موازی اند و می توانند با زمانهای موازی   اجرا گردند كه بسیار برای اجرای عملی كدهای RS مناسب و بهینه می باشند .

اگر تعداد خطاهای t كوچك باشد ، الگوریتم سریع اشاره شده در فوق  ممكن است خیلی موثرتر از روش تقسیم طولانی نباشد . اما هنگامیكه t بزرگ است ، این الگوریتم بسیار بهینه خواهد بود .

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

5-1- مقدمه :

 مقصود از شمای یك درمیان سازی چند بعدی (M-D)  مطرح شده در این فصل ، یك مفهوم جدید از این تكنیك بر پایه آرایه ها است كه از بسته بندی پی در پی جهت ساخت آرایه ها با سایز مورد نظر استفاده می شود . در نهایت نشان می دهیم كه این تكنیك می تواند هر خطای برست  را در خلال آرایه  بطور موثر همراه با خطاهای رندم ساده تواماً  تصحیح كند . مزیت این الگوریتم این است كه با یك بار اجرا قادر به تصحیح فوق است و هزینه محاسبات پائین می آید .

معرفی :

روش یك درمیان سازی یك بعدی و مزایای آن در فصول قبل مطرح گردید . در این فصل ابتدا این تكنیك را در حالت دوبعدی و سه بعدی (2-D , 3-D )  بررسی می كنیم و سپس آنرا برای حالت چند بعدی( (M-D تعمیم خواهیم داد . بعضی كاربردهای  این روش عبارتست از : ذخیره سازی اطلاعات نوری و مغناطیسی ، (CCD : charged-coupled deviced) ها ، باركدهای دو بعدی ، مخفی سازی اطلاعات در تصاویر دیجیتالی و نیز حذف خطای برست منتشر شده بصورت دسته ای در ترتیبات صوتی و تصویری (مقصود اصلی این پروژه).

هدف اصلی از بین بردن برست های منتشر شده در كلمات كد چندتایی است كه باعث برهم زدن سمبل های كلمه كد در هنگام دریافت آنها می شود .

خطاهای رخ داده در خلال كلمات كد ( خطاهای رندم ) با تكنیك های مختلف قابل FEC‌ تصحیح است . در واقع گسترش روش یك درمیان سازی یك بعدی به M‌ بعدی جهت تصحیح توام خطاهای برست و رندم ، بهینه است . در روش های یك در میان سازی مطرح شده تاكنون ، برای تصحیح هر خطای برست با طول   به الگوریتم مخصوصی احتیاج است و درصورتیكه اندازه برست افزایش یابد ،  ، به الگوریتم جدید با پارامتر های اضافه شده جهت تصحیح خطای برست نیاز است و درصورتیكه این اندازه كاهش یابد  الگوریتم ارائه شده برای برست با سایز بهینه نخواهد بود . در عمل معمولاً اندازه برست ایجاد شده ثابت نبوده و بنابراین الگوریتم های مطرح شده را بسیار محدود می كند . با درنظر گرفتن سایر آرایه های دو بعدی ( مثلاً برای فیم های صوتی وتصویری و تصویر ) مشكل مطرح شده ، حل خواهد شد . این روش به اختصار SP(successive packing) نامیده می شود . كه در حالت دو بعدی با آرایه های مربعی  ( در حالت كلی  ) قابل دستیابی است .

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

فلسفه تكنیك یك درمیان سازی در برخورد با برست هایی از M-D خطا ، بسیار شبیه حالت 1-D است عناصر در یك آرایه M-D آرایه ای دوباره مرتب می شوند و بنابراین خطاها تاحد ممكن در یك آرایه یك درمیان شده M-D آرایه ای ، از آرایه دور می شوند و تصحیح خطای برست درصورتیكه تنها یك خطا در هر آرایه یك درمیان شده وجود داشته باشد ، بسیار ساده تر می گردد .

تعریف 4-1 :درصورتیكه C را یك كد M-D دارای عناصر  تحت GF(q)  باشد ، كلمه كد از C یك آرایه M-D تایی از  است كه هر عنصر از آرایه M-D  به یك سمبل كد اختصاص می یابد .

(لازم به یادآوری است كه GF(q) به میدان Galois با q عنصر اشاره می كند كه ساده ترین حالت آن GF(2)={0,1} است)

تعریف 4-2 : در آرایه دو بعدی عناصر مجاور  (x,y) بصورت (x+1,y),(x-1,y),(x,y+1),(x,y-1) و در آرایه سه بعدی عناصر مجاور  (x,y,z) بصورت (x+1,y,z),(x-1,y,z),(x,y+1,z),(x,y-1,z),(x,y,z+1),(x,y,z-1)  نشان داده می شوند . بطور كلی برای آرایه M-D بعدی هر عنصر دارای 2M عنصر مجاور است .

تعریف 4-3 : هر برست ، كه زیر مجموعه ای از B آرایه M-D تایی باشد ، دارای حداقل یك مجاور در B است .

تعریف 4-4 : فاصله بین هر دو عنصر ، در واقع طول كوتاه ترین مسیر بین دو عنصر است . در اینجا مسیر شامل مربعی از اتصال عناصر مجاور از دو عنصر . با  اجرای تكنیك یك درمیان سازی ، هر عنصر سمبل های كد درگیر شده ، بعنوان یك خطای برست توزیع شده روی كلمات كد مختلف تلقی می گردد . اگر هر دو عنصر با یك فاصله كلمه كد در آرایه یك درمیان شده ماكزیمم گردد ، سپس تعداد زیادی خطای برست تصحیح می گردند .

 Aرا بعنوان یك آرایه M-D‌ با عناصر   با شاخص  ( برای آرایه دو بعدی  ) فرض می گیریم . اكنون بخشی از A را در یك بلوك L كه  در نظر می گیریم كه  . پس هر بلوك از K=N/L عنصر تشكیل شده است .

تعریف 4-5 : با روشفوق هر عنصر دارای یك شاخص k   با  است كه بلوك d ام نامیده می شود . با این تعریف می بینیم كه  دو عنصر معادل و   سه عنصر معادل اند . روشن است كه اگر عنصر معادل باشند ، عناصر معادلند اگر  در صورتیكه بلوك یك كلمه كد با طول K باشد سپس تمام عناصر در فاصله كلمه كد K معادل با سایر عناصر دارند .

از این رو  حل تكنیك یك درمیان سازی به حل مساله ماكزیمم و مینیمم فاصله بین عناصر  K معادل ، منتهی می گردد .

اگر برای هر k=0 تا M-1 ،  اولیه باشد ، سپس تعداد كلمات كدی كه متناظر با آرایه M-D تایی است ، می تواند شامل عدد صحیحی باشد كه در   ضرب شده است ، (n

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

تعریف 4-6 : یك آرایه یك درمیان شده B‌با سایز  در نظر می گیریم كه m‌ اولیه باشد . اگر حداقل فاصله بین هر دو سری عناصر m معادل ، ماكزیمم باشد ، سپس ما این آرایه را بعنوان آرایه پایه یك درمیان شده درنظر می گیریم .

پس با این تعریف می توانیم آرایه های پایه مربعی شده  و غیره را می توان ساخت .

تئوری 4-1 : آرایه دو بعدی   یك آرایه یك درمیان شده پایه است . براس ساخت یك آرایه یك درمیان شده پایه ، باید مرز فوقانی دارای حداقل فاصله باشد. توجه شود كه عناصر m‌ معادل از هر عنصر در آرایه مربعی ،‌ m-1  است . پس اگر m زوج و  باشد ، سپس مرز فوقانی دایره ، t‌ خواهد بود . و اگر m فرد و  باشد ، سپس مرز بالایی t خواهد بود . بعضی از مثالهای حالت دو بعدی در شكل 4-1 آمده است . با توجه به شكل دوایر با سایز m برای مقادیر 3,4,6,7,9,10,…‌موجود نیست ، پس مرز فوقانی با حداقل فاصله دایره ای است با سایز كوچكتر از m .

شكل4-1 : تعدادی از كروی های دو بعدی با سایز 2,5,8,13,18

با توجه به محاسبات مرزفوقانی 2 است برای  و 3 است برای  و غیره .

رویه 4-1 :

درصورتیكه A  یك آرایه دوبعدی با سایز  باشد و  مرز فوقانی فاصله بین هر دو عنصر باشد ، مختصات (i,j) را بعنوان مختصات هر عنصر مارپیچی یعنی اعداد صحیح مدول m تعریف می كنیم . و عناصر را در اولین ردیف بعنوان  با موقعیت های (0,0),(0,1),…,(0,m-1)   فرض می كنیم . سپس قرار می دهیم :

 –1 X=1 , Y=  .برای هر عنصر با موقعیت (i,j) ، 1‌ را به زیرنویس از این عناصر می افزاییم و آنرا در موقعیت (i+X,j+Y)  قرار می دهیم . برای مثال  را در موقعیت (X,Y) قرار می دهیم . این كار را تاجایی ادامه می دهیم كه تمام موقعیت ها اشغال گردد . اشكال زیر مثالهایی از این رویه را نشان می دهند .

شكل 4-2 : آرایه یك درمیان شده پایه                          شكل 4-3 : آرایه یك درمیان شده پایه

شكل 4-4 : آرایه یك درمیان شده پایه

تئوری 4-2 : اگر عدد صحیح m اولیه باشد ، سپس آرایه مربعی ساخته شده با رویه 4-1 یك آرایه یك درمیان شده پایه است .

در رویه 4-1 ما تكنیكی برای تولید آرایه یك درمیان شده پایه ارائه كردیم اكنون این روش را بسط داده و هر آرایه  كه دارای فاصله مینیمم بین هر دو سری عناصر m معادل باشند ، تولید می كنیم .

رویه 4-2 :

درصورتیكه A  یك آرایه دوبعدی با سایز  باشد و  مرز فوقانی فاصله بین هر دو عنصر باشد ، مختصات (i,j) را بعنوان مختصات هر عنصر مارپیچی یعنی اعداد صحیح مدول m تعریف می كنیم . و عناصر را در اولین ردیف بعنوان  با موقعیت های (0,0),(0,1),…,(0,m-1)   فرض می كنیم . سپس قرار می دهیم :

X=1  و Y‌ یك اولیه وابسته دارای شرایط    . برای هر عنصر با موقعیت (i,j) ، 1‌ را به زیرنویس از این عناصر می افزاییم و آنرا در موقعیت (i+X,j+Y)  قرار می دهیم . برای مثال  را در موقعیت (X,Y) قرار می دهیم . این كار را تاجایی ادامه می دهیم كه تمام موقعیت ها اشغال گردد .

تئوری 4-3: برای هر m>1‌ ، آرایه ساخته شده با رویه 4-2  ، دارای حداقل اصله بین هر دو سری عناصر m معادل  هستند .

5-4-آرایه های یك درمیان شده پایه مستطیلی :

تئوری 4-4 : آرایه مستطیلی  را در نظر می گیریم . اگر mn باشد ، مرز فوقانی این آرایه برابر مرز فوقانی آرایه   است .

رویه 4-3 :

درصورتیكه A  یك آرایه دوبعدی با سایز  باشد و  مرز فوقانی فاصله بین هر دو عنصر باشد ، اگر mn باشد ، رویه ای مشابه خواهیم داشت .

5-5-آرایه یك درمیان شده پایه سه بعدی (3-D)  :

تعریف 4-7 : یك آرایه سه بعدی B با سایز  كه  اولیه و  است د نظر می گیریم . اگر حداقل فاصله بین هر دو سری عناصر mn معادل وجود داشته باشد ، سپس این یك آرایه یك درمیان شده پایه است .

برای یك آرایه سه بعدی با سایز  با حداقل فاصله  ، مرز بندی زیر را داریم :

   كه m دارای سایز سه بعدی است . این روش را می توان برای آرایه M-D بعدی تعمیم داد .

شكل 4-5: یك آرایه یك درمیان شده پایه سه بعدی

- بسته كردن پی در پی با آرایه یك درمیان شده پایه  :

در این بخش یك تكنیك یك در میان سازی M-D‌ بعدی را بر پایه بسته كردن پی در پی با آرایه یك درمیان شده پایه بررسی می كنیم . سپس  این روش در تصحیح خطای برست منتشر شده مورد آنالیز قرار می گیرد .

-بسته كردن پی در پی : اكنون ما تكنیك SP‌ را در مورد M-D مورد بررسی قرار می دهیم .

رویه 4- 4 : یك در میان سازی M-D‌ با استفاده از بسته كردن پی در پی : یك آرایه M-D‌ با عناصر   در نظر می گیریم . این آرایه خودش یك آرایه اصلی است اگر  و

 كه  یك عنصر از آرایه ‌ است . زیر نویس  به تعداد عناصر آرایه اشاره می كند . با داشتن آرایه  با سایز  ، آرایه  بوسیله انتقال هر عنصر  در  به یك آرایه M-D با عملیات  ، تولید شود . این رویه بسته كردن می تواند بطور متوالی برای ساخت آرایه  ادامه یابد .

مثالهای از این روش در اشكال زیر  آورده شده است .

شكل 4-6 : استفاده از بسته كردن پی در پی برای تولید آرایه یك در میان شده

شكل 4-7 : استفاده از بسته كردن پی در پی برای تولید آرایه یك در میان شده

برای تولید یك آرایه یك درمیان شده با سایز دلخواه ، از روش بسته كردن پی درپی استفاده می كنیم بر پایه تركیبی از آرایه های مختلف پایه . بعنوان مثال آرایه های یك در میان شده   . كه می توان با استفاده از آنها آرایه یك درمیان شده  را بوسیله  تولید نمود . (مثال : شكل 4-8 )

شكل 4-8 : استفاده از بسته كردن پی در پی برای تولید آرایه یك در میان شده

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

تعریف 4-7 : برست های را با سایز های مساوی و در شكل آرایه یك درمیان شده M-D بعدی را در نظر می گیریم . اگر هر عنصر در یكی از این دو برست ، معادل عنصر دیگر در برست دوم باشد یا بعبارت دیگر ، K معادل از یك عنصر از برست دوم باشد ، آنگاه گفته می شود كه برست های  ، برست های K  معادلند . در ادامه این فصل در مورد تصحیح خطای برست بحث خواهیم كرد .

فرض می كنیم كه عناصر معادل تعریف شده در فوق یك كلمه كد M-D‌ بعدی است . این روشن می سازد كه كلمه كد شامل یك مجموعه ای از سمبل های كد پی در پی (نتیجه ای ) است .

یك خطای برست در یك آرایه یك درمیان شده گفته می شود كه منتشر شده است (spread) و می تواند با كدهای تصحیح كننده خطای رندم تكی تصحیح شود ، اگر هر عنصر در برست در كلمات كد منتشر شده باشد . از این دید اگر دو برست داشته باشیم  و یكی یك درمیان شده باشد ، بایستی دومی نیز یك درمیان شده باشد و نتیجه گیری زیر را خواهیم داشت :

اصل موضوع 4-1 : اگر A‌ یك آرایه دوبعدی با سایز  باشد كه بوسیله بسته كردن پی درپی یك آرایه پایه یك درمیان شده با سایز   ساخته شده باشد ، سپس تمام برست های با سایز   در A با k

تئوری 4-5 : یك آرایه دو بعدی  A‌ با سایز   در نظر می گیریم . سپس  هر برست با سایز  با  در یك آرایه یك درمیان شده A‌ كه با استفاده از بسته كردن پی درپی ساخته شده است ، هر عنصر آن در بلوك با سایز  قرار خواهد گرفت . این تئوری روشن می سازد كه اگر یك سمبل كد به هر عنصر در هر بلوك اختصاص یابد ( مطابق تعریف 4-5 ) و تمام سمبل های كد با یك كلاسی از K‌ تعریف گردد ، سپس تصحیح خطاهای برست با كدهای تصحیح كننده خطای رندم تكی تضمین خواهد شد .

همچنین  با تكنیك بسته كردن پی در پی درجه یك درمیان سازی در مرز پائینی ( گین یك درمیان سازی ) قرار خواهد گرفت  و این تكنیك بهینه خواهد بود  .

تخمین 4-1 : درصورتیكه A ‌  یك كد M-D دارای عناصر  باشد سپس هر برست با سایز  با  در آرایه A‌ با استفاده از بسته كردن پی در پی بدست می آید .

رویه 4-5 :

 -  با تكنیك SP آرایه یك درمیان شده   تولید می گردد .

- آرایه یك درمیان شده  بصورت زیر تولید می گردد : 

اصل موضوع 4-2 : C  را دسته ای با سایز 2m در آرایه ای دوبعدی با سایز   در نظر می گیریم ، بطوریكه :  .

بنابراین می توان یك آرایه ( بلوك ) مستطیلی  با سایز   یا / و  یك آرایه مستطیلی  با سایز   در نظر گرفت بطوریكه C در یكی از دو آرایه مستطیلی فوق الذكر تا در هر دوی  آنها قرار گیرد .

تئوری 4- 6 : آرایه های دوبعدی تولید شده با رویه 4-5 بهینه هستند و می توانند برست منتشر شده با سایز 2m در یك كلمه كد مشخص با سایز  را تصحیح كنند .

این تئوری ابراز می دارد كه اگر یك سمبل كد مشخص به هر عنصر در بلوكی با سایز اختصاص یابد ، ( مطابق تعریف 4-5) و تمام سمبل های كد را در بر بگیرد ، با بكار گیری تكنیك SP می توان تمام خطاهای برست با سایز 2m را با كدهای تصحیح كننده خطای رندم تكی ، تصحیح نمود . بنابراین این روش بهینه برای مجموعه های برست بزرگ است كه با ابزاری تغییر یافته به تصحیح برست می پردازد .

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

6-1-مقدمه :

كدهای محصول كه در بخش 1 تشریح شده اند ، از عمومی ترین كدهای بكار رفته در مكانیسم تصحیح خطا در كاربردهای ارتباطات صوتی وتصویری است كه جهت تصحیح خطاهای رندم و برست بكار می رود . شكل 5-1 یك آرایه  ،  در میدان F=FF(q) را نشان می دهد كه جهت انكدینگ كد محصول حاصل از دو كد خطی است كه عبارتند از :

كد  در ردیف ها ،   تحت F و  كد  در ستون ها ،   تحت F  .

شكل 5-1 : یك آرایه  از كد محصول

در كل ساختار افزونگی صفر ( كه این كد محصول را به آن نام نامیده ایم ) ، بصورت زیر است :  (5-1 )   

كدهای خطی ستونی و ردیفی ، ماكزیمم فاصله قابل تمایز (MDS) مانند كدهای Read –Solomon را می گیرند كه عبارتند از :  ،  . در این مدل فرض شده است كه مقادیر خطا بر آرایه منتقل شدة  تاثیر گذار است و حاصل آرایه   خواهد شد . و احتمال تصحیح  خواهد شد . اگر از این مقدار خارج باشد ، مقدار بدست آمده دارای انحراف زیادی است . میزان خطا را با  تعریف می كنند . بیشتر پترن خطا در این بخش ، خطای برست در نظر گرفته شده است .

فرض می كنیم آرایه   ردیف به ردیف منتقل شده است . بنا به طبیعت خطای برست ، انتظار می رود كه این خطاها بر T ردیف تاثیرگذار باشند ، كه احتمال Prob{T=t} وابسته به كانال و انتخاب  است . اگر i امین ردیف در  تحت تاثیر خطا قرار گرفته باشد ، بردار خطا در i امین  ردیف از آرایه خطای E قرار خواهد گرفت . بردار خطا غیر صفر خواهد بود اگر و تنها اگر ردیف های مذكور در  خراب شده باشند .

یك استراتژی دیكدینگ برست برای ساختار صفر در زیر آورده شده است :

كد  ابتدا جهت آشكارسازی ردیف های دارای خطا در روشی كه بطور مختصر توضیح خواهیم داد ، بكار می رود . با داشتن ردیف های دارای اشكال ، دیكدر  ، كدهای  را ستون به ستون دیكد می كند .اكنون تمام موارد دارای اشكال در ستونها بعنوان پاكشدگی تلقی می گردد . اگر p‌ بعنوان احتمال پذیرش اشكال در دیكدینگ باشد ، سپس نصف این احتمال بعنوان احتمال تعداد خطاهای قابل تصحیح در نظر گرفته می گردد . در عمل اگر  یك كد MSD باشد ، سپس برای  خواهیم داشت : (5-2)  . این مرز ، توانایی تحیح پاك شدگی  را تضمین می كند . همانگونه كه ذكر شد،  ردیف های دارای اشكال را با محاسبه آشكار می كند ، برای هر ردیف ، سیندرم محاسبه می گردد . اگر  تعداد موارد تاثیر گذار بر ردیفها باشد و  ، سپس سیندرم محاسبه شده برای ردیف ها بایستی برای ردیفهای دارای اشكال ، غیر صفر باشد .در سایر موارد اگر  باشد ، سپس هر ستون   در ماتریس پریتی چك  از  ، بطور غیر خطی غیر وابسته است و احتمال اینكه هر ردیف دارای سیندرم تمام صفر باشد ،  خواهد شد . بنابراین علیرغم مقادیر تاثیرگذار بر ردیفهای دارای اشكال ، احتمال آشكار نشدن این ردیف ها ، كمتر از  خواهد بود . و در مجموع احتمال اینكه ردیفی در آرایه داده شده ، هم دارای اشكال باشند و هم آشكار نشوند ، برابر است با :  در این رابطه  مقدار   را می گیرد . و با توجه به رابطه 5-2 داریم :      (5-3)

بعنوان نمونه اگر در هر رخداد كه تعداد ردیف های تحت تاثیر T كوچكتر از   باشد ، ما در واقع می توانیم به دیكدر از  اجازه دهیم كه بعضی از ردیف های دارای اشكال را آشكار نكند و مزیت آن در این است كه سمبل های افزونگی به اندازه  در  باقی می ماند . و از آن جهت اختصاص ردیف های دارای اشكال و آشكار نشده استفاده می گردد . بنابراین علاقه مند هستیم كه  تا حد ممكن كوچك باشد ، تا تعداد مقادیر تاثیرگذار توسط دیكدر ، جهت پاك شدن مارك زده شوند و در این صورت افزونگی به حداقل خواهد رسید . به همین دلیل بالعكس   و نتیجتاً  حداكثر مقدار مطلوب است . و بنابراین دیكدر  جهت تصحیح پاك شدگی های بیشتر ، پیچیده می گردد. مرز  با میزان حافظه و دوره عكس العمل محدود خواهد شد .

هدف اصلی ما در این بخش افزایش ابعاد كد است تاوقتیكه احتمال خطای دیكدینگ برای برست ها ، باقی بماند .

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

فرض كنید كه كدهای  و  ، كدهای MSD در F=GF(q)  باشد كه از ساختار صفر استفاده می كند :

  و   ماتریس پریتی چك   از   باشد . 

 آرایه ای با  ستون خواهد بود كه با كلمات كد از  باشد . بطور غیر مشابه با ساختار صفر در اینجا هر ردیف  یك كد مشخص را شروع نمی كند . برای هر ردیف  سیندرم با جایگزینی  با آرایه ای به شكل   :   كه :   است ، در نظر می گیریم .

اكنون فرض می كنیم كه  در یك كانال نویزی انتقال می یابد و پاسخ آرایه  باشد ، در پایان دریافت ، سیندرم به شكل  :   در می آید . سیندرم آرایه دریافت در شكل 5-2 آمده است .

شكل 5-2 : سیندرم آرایه دریافت شده

 را با   مقایسه می كنیم و آرایه تفاضل سیندرم   را بدست می آوریم . نتایج زیر حاصل می گردد :

1-       اگر بردار دریافت شده در  غیر صفر باشد ، ردیف متناظر در  دارای اشكال است.

2-       اگر ردیف داده شده در  تمام صفر باشد ، احتمال اینكه ردیف متناظر در   دارای اشكال باشد ، كمتر از    است .

از این رو اگر شرط 5-3 ارضا گردد ، سپس با احتمال ، ردیف های غیر صفر از  به تمام ردیف های دارای اشكال در   اشاره می شود . درصورتیكه ستونهای  ستونهای S باشد ، فرستنده هر ردیف اطلاعات  را انكد كرده و سپس هر بردار ستونی  در آرایه سیندرم حاصل از S یك كلمه كد  از یك MDS  :  در GF(q) خواهد بود . انتخاب مقادیر افزونگی باید به گیرنده اجازه دهد كه هر ردیف غیر صفر در  خارج از  را با احتمال قابل پذیرشی از خطا جای دهد . یك انتخاب ساده برای  كه می توان بعنوان باقیمانده فرض گرفت عبارتست از : . برای هر j  است كه  شرط 5-2 را ارضا كند .این شرط روشن می سازد كه با احتمال  تعداد ردیف های غیر صفر در  از  تجاوز نمی كند . بنابراین در این مورد با دیكدینگ ستون های  ، دیكدرهایی از  می توانند ردیف های غیر صفر  را جای دهند . و بنابراین ردیف های دارای اشكال شده   با احتمال   خواهد شد . اكنون هر بردار ستونی از   یك تركیب خطی از    خواهد بود . هر ستون    یك بردار كد  است . مادامیكه  خطی باشد ، هر ستون  یك كلمه كد از كد  ، MSD   خواهد بود كه افزونگی آن  . اگرچه به افزونگی   احتیاج است تا یك كد MDS شود . و ساخت تمام افزونگی ها درS  برابر خواهد بود . اگر ما هر كلمه كد را بعنوان زیر مجموعه ای از كد   در نظر بگیریم ، افزونگی  بطور خطی بدست خواهد آمد و احتیاج به افزونگی  در S با انكد آرایه   قابل دست یابی است و به آن ساختار 1 می گوییم .

قضییه 1 : افزونگی در ساختار 1 برابر است با :( 5-4 )  . از این رو افزونگی ساختار 1 بسیار مطلوب است جهت مقایسه با رابطه 5-1 وقتیكه :  . در عمل وقتی   و  باشد ، كاهش افزونگی به فاكتور 2 از مقایسه با ساختار صفر می انجامد.

در زیر خلاصه از ساختار 1 مطرح گردیده است : در صورتیكه  و  مانند ساختار صفر و ماتریس پریتی چك آنها نیز به ترتیب  باشد كه :  ردیف های  را مشخص می كند . برای  در صورتیكه  و  یك كد MDS در GF(q) با  باشد ،ماتریس پریتی چكا مشخص خواهد كرد . كه در ساختار 1 شامل تمام  آرایه  برای   بطوریكه  است . سیندرم هر ردیف  محاسبه می شود با ماتریس پریتی چك  و یك آرایه  از  خواهد بود كه هر ستون  یك كلمه كد از  است . هر ستون در  یك كلمه كد از از  است و داریم : (5-5)  .

شكل 5-3 رویه انكدینگ ساختار 1 را نشان می دهد .

شكل5-3 : رویه انكدینگ ساختار 1 .

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

با توجه به رویه دیكدینگ ، برای تمام ، دیكدر پاس می شود به دیكدر  پاك كردن اطلاعات از ستون های كه پراسس شده اند . بنابراین تصحیح خطا از  با این پیشینه ، راحت تر می شود و این امكان پیدا می شود كه ترتیبی از كدهای  طراحی گردد ،   ، پس افزونگی از كدها عموماً با افزایش j  كاسته می شود . در نهایت اطلاعات پاك شده پاس می شود بوسیله دیكدر  به دیكدر  كه شامل قرار گرفتن تمام ردیف های دارای اشكال در  است ، بنابراین ما یك حالت پیش رونده گذرا را از تصحیح خطای كامل برای  خواهیم داشت . با تصحیح خطای پاك شدگی برای  و   داریم :  . پاسخ شمای كدینگی با نام ساختار 2 خواهد بود كه تمام افزونگی آن برابر است با :

  . در بیشتر موارد ما به حداقل  سمبل افزونگی برای دیكد تمام مقادیر احتیاج داریم. بنابراین افزونگی ساختار 2 نسبت ساختار 1 كاهش یافته است . شكل 5-4 شمایی از انكدینگ ساختار 2 را نشان می دهد.

شكل 5-4 : رویه انكدینگ ساختار 2 .

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

در ساختار های فوق الذكر تنها توانایی آشكارسازی كد  برای ردیف های دارای اشكال مطرح گردید . در این بخش ساختاری مطرح می گردد كه علاوه بر عملكردی مشابه ساختار 2  جهت آشكار سازی خطاها ، توانایی تصحیح بعضی از آنها را نیز در ردیفها داشته باشد . این موارد در كانال هایی كه هردوی خطاهای رندم و برست را داشته باشند رخ می دهد . پاسخ ، ساختاری بنام ساختار 3 است . پارامتر  را بعنوان تعداد خطایی از كد باید تصحیح گردند ، در نظر می گیریم . متغییر رندم  تعداد ردیفهایی تحت تاثیر مقادیر بیشتر از  نباشند و متغییر رندم  تعداد ردیفهایی تحت تاثیر مقادیر بیشتر از  باشند ، در نظر می گیریم . روشن است كه  . هر ستون در آرایه یك كلمه كد  خواهد بود . و انتظار داریم كه

 5-6 )  گردد . كد  احتیاج دارد به تصحیح پاك شدگی فقط در آن ردیف هایی كه شامل بیش از باشد .  را بعنوان پارامترهای  برای تمام ردیف های تاثیر گذار بر ساختار 3 تعریف می كنیم و  5-7 )  .

احتمال اینكه ردیفی تصحیح برابر است با 5-8 )  . با داشتن مقداری از  ، یك خطای دیكدینگ اتقاق می افتد تنها اگر تعداد ردیف هایی كه بوسیله  تصحیح نشده اند از  تجاوز كند . و در اینصورت تمام افزونگی ساختار 3 برابر می شود با :  . در نهایت از دیكدرهای  جهت بازیابی آرایه سیندرم تفاضلی  برای آرایه دریافت شده  استفاده می كنیم . در اینجا به بازیابی تمام مقادیر ( نه فقط ردیف های غیر صفر ) احتیاج داریم و بنابراین با داشتن  ، هر ردیف آن بعنوان یك سیندرم خواهد بود و دیكدر  برای  خطا در هر ردیف  اضافه می گردد . دیكدینگ موفقیت آمیز خواهد بود اگر حداكثر  ردیف دارای اشكال   وجود داشته باشد .

شكل 5-5 : آرایه ای در ساختار 3

این متن فقط قسمتی از كدهای بلوكی و كدهای كانولوشن می باشد

جهت دریافت کل متن ، لطفا آن را خریداری نمایید

قیمت فایل فقط 1,800 تومان

برچسب ها : كدهای بلوكی و كدهای كانولوشن