بخشی از مقاله
چکیده
کد کشف و تصحیح خطای پرسک - Persec Codes - نخستین بار در سال 2007 میلادی معرفی شد. تفاوت و امتیاز اصلی این روش نسبت به دیگر روشهای کشف و تصحیح خطای این است که در صورتی که نتواند در یک بسته بزرگ داده دقیقا بیت خطا را مکانیابی کند، تنها چند بیت را بهعنوان بیت مشکوک تعیین میکند تا نیازی به ارسال مجدد کل داده نباشد. البته دیگر امتیاز این روش آن است که دقت تصحیح کد پرسک بسته به میزان بیتهای سرباری قابل تنظیم و در دست طراح است. در این مقاله ضمن تعریف کد پرسک، مدارهای منطقی فرایند کدگذاری و کدگشایی آن نیز ارایه خواهد شد. این مدارات دادهها را بهصورت برخط پردازش میکنند.
-1 مقدمه
رخداد خطا در دادههای دیجیتالی بههنگام انتقال در شبکههای ارتباطی کامپیوتری یکی از مشکلات مهم و البته اجتنابناپذیر است. از اینرو سیستمهای انتقال داده ناگزیر از بهکارگیری یکی از ابزارهای تحملپذیر در برابر خطا1 برای کشف و تصحیح خطا2های احتمالی هستند تا اطلاعات بهصورت صحیح و مصون از خطا انتقال یابد. خطاهای وارده بر دادهها بهدلایل گوناگون رخ میدهند. برخی از آنها بهدلیل وجود میدان مغناطیسی، تاثیرات الکتریکی و اقلیم - مانند توفان، گردباد و پرتوهای خورشیدی - پدید میآیند و ممکن است که در هر دو نوع ارتباط کامپیوتری درونی - مانند انتقال از پردازنده به حافظه - و بیرونی - مانند مخابرات ماهوارهای و شبکههای بیسیم - تاثیر بگذارند.
بدین منظور تاکنون روشهای بسیاری ارایه شدهاند که از میان آنها میتوان روشهای کدتوازن3، کد برگر4 و کد جمعآزما3] 5،1و[4 برای کشف خطا، روشهای کد چرخشی5] 6و[6، کد همینگ[7] 7، کد باقیمانده2] 8و[8، کد نوردستورم-رابینسون[9] 9 و توربوکد[10] 10 برای تصحیح یک بیت خطا و روشهای کد [13-11] 11BCH و کد باقیمانده - گسترشیافته - 14]و[15 برای تصحیح چند خطا را نام برد. هر یک از این روشها در برخی شرایط بهتر کار میکنند؛ اما هیچیک برای همه شرایط مناسب نیستند و طراحان باید با در نظر گرفتن شرایط و محدودیتهای سیستم خود یکی از این روشها را برگزینند.
کد پرسک نیز روشی برای کشف و تصحیح خطاست که در سال 2007 توسط شاهمیری و همکاران ارایه شد .[16] فرایند تصحیح خطا در این روش، انعطافپذیر است و میتوان با توجه به میزان سرباری یا زمان پردازش قدرت و نسبت تصحیح در آن را تنظیم کرد. در همه این روشها با گسترش حجم، سرعت و پیچیدگی پیادهسازی سختافزاری، بازدهی کلی سیستمهای مخابراتی کاهش مییابد و از اینرو نیازی حیاتی به پیدایش روشهای نوین یا بازنگری روشهای قدیمی احساس میشود .[17]
یک روش کشف و تصحیح خطا یک تابع ریاضی است [3] که بهطور معمول در قالب یک ابزار سختافزاری پیادهسازی میشود. کد توازن یکی از مهمترین روشهای کشف خطاست که کدگذاری12، کشف خطا و کدگشایی13 در آن بسیار سریع بوده و تنها یک بیت سرباری14 به هر بسته داده - معمولا یک بایت - میافزاید و میتواند رخداد تعداد فردی از خطا را در داده کشف کند .[2] کد همینگ نیز یکی از پرکاربردترین روشهای تصحیح خطا است که تعداد c بیت سرباری را به هر بسته k بیتی داده میافزاید؛ بهگونهای که: 2c = 4] k + 1و.[7 این مقدار بیت سرباری برای بستههای بزرگ داده ناچیز است اما افزایش زمان فرایند تصحیح و البته کاهش دقت را بهدنبال دارد.
در ادامه مقاله نخست در بخش 2 واژگان و اصطلاحات مورد نیاز برای معرفی کد پرسک شرح داده خواهد شد. سپس در بخش 3 با ذکر یک مثال روش کار کد پرسک توضیح داده میشود. در بخش 4 رفتار این روش از دیدگاه ریاضی و احتمالات بههمراه نتایج آزمونها و شبیهسازی کامپیوتری و مقایسه آنها ارایه میگردد. در بخش 5 نیز سختافزار مورد نظر برای فرایندهای کدگذاری و کدگشایی کد پرسک معرفی میشود و سرانجام در بخش 6 نتیجهگیری و پیشنهاد برای کارهای آینده ارایه خواهد شد.
-2 تعاریف
در دوران شاهنشاهی هخامنشی، ارتش حرفهای ایران را »سپاه جاویدان« مینامیدند. این سپاه از آنرو »جاویدان« خوانده میشد که شمار سپاهیانش همواره ده هزار تن ثابت بود و پس از هر نبرد زخمیها در صورت امکان، بهکمک یک گروه ویژه پزشکی درمان میشدند و بهجای کشتگان و یا زخمیان بیبازگشت، جنگاوران آزموده تازه نفس جایگزین میگشتند. روش کار کد پرسک به سپاه جاویدان بسیار همانند است.
داده - سپاه - با طول ثابت قراردادی بهسوی هدف حرکت میکند و اگر در راه رسیدن به مقصود از محیط، اختلال15 - جنگ - بر آن وارد شود و بر برخی از بیتها خطا رخ دهد - برخی از سپاهیان گزند بینند - گیرنده بهکمک دادههای سرباری - گروه پزشکی - برای صحت آنها میکوشد و دادههای درست - افراد سالم - را جدا کرده، تنها بیتهای ناسالم یا با وضعیت نامشخص - کشتهها و زخمیان - را از فرستنده درخواست میکند - نیروی تازه نفس میطلبد - . با این توصیف، واژگان کلیدی مورد نیاز برای شناخت و معرفی کد پرسک بهشرح زیر تعریف میگردد: بسته داده :16 - P - عبارت است از دادهای با طول ثابت که باید بهطور سالم از فرستنده به گیرنده برسد.
طول داده :17 - L - عبارت است از طول کل داده مورد نیاز برای انتقال، بدون در نظر گرفتن دادههای سرباری. پایه :18 - n - بر پایه الگوریتم کد پرسک، پیش از کدگذاری، میبایست عددی بزرگتر از 2 بهعنوان پایه توسط سیستم برگزیده شود. پایه نقشی مهم در کد پرسک بازی میکند و مانند سرند در جدا کردن دانههای بزرگ و کوچک عمل میکند و هر چه مقدار آن افزایش یابد، همچون سرندی با تعداد لایههای بیشتر و تورهای ریزبافتر، خطاها را بهتر جدا میکند. هرچه مقدار پایه افزایش یابد، دقت، سرباری و زمان پردازش افزایش خواهد یافت و از اینرو باید بسته به شرایط سیستم، با دقت تعیین شود. لازم بهذکر است که پایه 1 در این روش در حقیقت برابر با کد توازن عادی است.
سرباری :19 - R - عبارت است از مجموعه بیتهای افزوده برای کمک به فرآیند تصحیح. بیتهای نگهبان :20 - g - عبارت است از n-1 بیت صفر - یا یک - که بهطور قراردادی به آغاز و پایان داده افزوده میشود تا همه بیتهای اصلی داده توسط الگوریتم بررسی گردد. قطعه :22 - S - با توجه به الگوریتم کد پرسک، در هر مرحله از فرایند کدگذاری یا کدبرداری، بسته داده به قطعههای n بیتی پیاپی تقسیم میگردد.
محتوای بیتی هر یک از این قطعات یک عدد باینری بین صفر و 2n-1 خواهد بود. دور :22 - i - الگوریتم کد پرسک برخی از محاسبات را n بار - دور - بر بسته داده انجام میدهد. بیتهای مشکوک :23 - h - بر پایه روش کار کد پرسک، بسته داده به قطعههای n بیتی تقسیم میشود و در صورت وجود خطا، به یکی از بیتهای برخی از قطعهها مشکوک میگردد. این فرایند n بار بر روی کل داده انجام میپذیرد. بیتهای بازفرست :24 - r - پس از پایان کار الگوریتم، یکی از حالتهای زیر پیش میآید:
-1 تنها یکی از بیتهای بسته داده n بار مشکوک قلمداد شود؛ که آن بیت خطا بوده و مکان آن تعیین میشود.
-2 هیچ بیتی n بار مشکوک تلقی نگردد؛ که نشان داده خواهد شد، چنین حالتی امکانپذیر نیست؛ مگر اینکه بیش از یک خطا بر داده رخ داده باشد.
-3 چند بیت n بار مشکوک بهشمار آید؛ که آنها را بیتهای بازفرست مینامیم و در این حالت نمیتوان جای دقیق خطا را تعیین کرد، اما بهجای ارسال مجدد کل داده، با فرستادن این چند بیت - که تعداد آنها نسبت به کل داده ناچیز و بیت خطا حتما در آن موجود است - صحت آن تامین میشود. دامنه :25 - d - فاصله جایگاه یک بیت خطای فرضی تا انتهای قطعه مربوطهاش را دامنه مینامیم. در کد پرسک، همه پارامترهای تعریفشده در بالا، نسبت به دقت و سرعت دلخواه، انعطافپذیر و قابل تنظیم هستند.
-3 کد پرسک
کد پرسک بهطور کلی با الهام از تکنیک کد توازن اما بر پایه الگوریتمی کاملا جدید کار میکند و در حقیقت تکامل ویژهای از آن روش است. کد توازن که انتخابی مناسب برای انتقال دادههای درون کامپیوتر است، یک بیت داده را بهگونهای به بسته میافزاید که تعداد یک - یا صفر - های درون بسته همواره زوج - یا فرد - باشد .[1] کد توازن برای کشف یک - یا تعداد فرد - خطا روشی مطمئن است، اما برای مخابرات راه دور با بستههای بزرگ، که ممکن است چند خطای همزمان در آن رخ دهد، توصیه نمیشود.
البته این روش توان مکانیابی یا بهعبارت بهتر تصحیح خطا را ندارد. کد همینگ، کد باقیمانده و نیز کد BCH برای هر دو گونه ارتباطات درون و بیرون کامپیوتر بهکار میروند؛ اما برای پردازش بستههای بزرگ ارسالی زمان بالایی مصرف میکنند 19]و.[20 کد پرسک برای مخابرات راه دور با بستههای بزرگ مناسب است و برای دادههای کمحجم که در ارتباطات درونی بهکار میرود، توصیه نمیشود. این روش توان تصحیح خطا را نیز دارد و مهمترین ویژگیاش مکانیابی بیت بازفرست در هنگام فرایند تصحیح است.
در روشهایی که تاکنون ارایه شدهاند، بسته به شرایط، گاه خطا کشف و تصحیح میشود و گاه روش مربوطه از کشف یا تصحیح خطا درمیماند. اما کد پرسک راه حل دیگری نیز دارد. این روش همیشه خطاها را کشف میکند، اما گاه بهجای مکانیابی دقیق بیت خطا برای تصحیح، چند بیت خطا را - که حتما یکی از آنها بیت خطا است - تعیین میکند. بنابراین سیستم فرستنده فقط چند بیت را دوباره میفرستد .[16]
-1-3 ساختار روش
پس از انتخاب عدد پایه - n - ، بسته داده به بخشهای n بیتی تقسیم میشود. برای نمونه اگر بستهای 64 بیتی با پایه دلخواه 3 داشته باشیم، این بسته داده به 21 بسته 3 بیتی تقسیم میشود و 2 بیت بیمصرف باقی میماند. برای اینکه در این مرحله و در گامهای بعدی روش، بیتهای داده اصلی بیمصرف نمانند، تعداد n-1 بیت نگهبان با مقدار همیشه صفر - یا یک - به آغاز و پایان بسته داده افزوده میشود. این بیتها پس از دریافت در دستگاه گیرنده و اطمینان از درستی داده، حذف خواهند شد. بنابراین اکنون بسته دادهای 68 بیتی در قالب 22 بسته 3 بیتی و باز هم 2 بیت اضافه موجود است، که البته اینبار این دو بیت مهم نیستند، چون آنها تنها بیتهای نگهبان هستند .[16]
-2-3 کدگذاری کد پرسک
هر بسته بیتی از داده، عددی از صفر تا 2n-1 - برای مثال در پایه 3، اعداد اکتال از 0 تا - 7 میسازد و تعداد هر یک از این اعداد در کل بسته، عددی زوج یا فرد خواهد بود. در کد پرسک به هر یک از این مجموع اعداد یک بیت توازن - در مجموع 2n بیت توازن - تعلق میگیرد. سپس باید تعداد هر یک از این اعداد بر پایه n محاسبه شده، بیت توازن - زوج یا فرد - متعلقهشان نیز تعیین شود. اما کار کدگذاری در اینجا بهپایان نمیرسد و این فرایند باید در مجموع n دور - هر بار با یک بیت انتقال بهسمت راست نقطه آغازین بخشبندی بستهها - انجام شود. روشن است که بر پایه n، تعداد n مجموعه 2n بیتی و در نتیجه n×2n بیت توازن به ازای کل داده بهدست میآید .[16]
-3-3 فرایند کشف خطا
دستگاه فرستنده باید این n×2n بیت داده سرباری را بههمراه داده برای گیرنده بفرستد. گیرنده این بیتها را دوباره تولید میکند و آنرا با بیتهای دریافت شده مقایسه میکند. اگر اختلافی میان آنها نباشد، میتوان گفت داده سالم به مقصد رسیده وگرنه خطا - ها - یی در آن رخ داده است. روشن است اگر خطایی در داده اعمال شود، تعداد برخی از اعداد بر پایه n تغییر میکند و در حقیقت در هر مجموعه، از تعداد یکی از آن اعداد کم و به یکی دیگر افزوده میشود. هنگامی که گیرنده این دو مجموعه بیتهای توازن قدیم و جدید را با یکدیگر مقایسه میکند، درمییابد که کدامیک از این اعداد به دیگری تبدیل شدهاند، زیرا این تبدیل، بیت توازن مربوطه را متاثر ساخته است .[16]
-4-3 فرایند تصحیح خطادر هنگامی که رخداد یک بیت خطا را بررسی میکنیم و تعدادی عدد بر پایه n - 2n بیتی - مشکوک داریم که به عددی دیگر تبدیل شدهاند، در حقیقت حداکثر یکی از بیتها مشکوک بهخطاست و بیتهای دیگر مبرا هستند؛ زیرا شک به آنها مستلزم رخداد بیش از یک بیت خطا است. برای نمونه، با پایه n=3 - عدد اکتال - هیچگاه یک - 000 - 0 به - 111 - 7 تبدیل نمیشود؛ زیرا این تغییر مستلزم 3 بیت خطا است.د بر مبنای 2n تبدیل شده در هر دور را بهکمک یک جدول درستی27 مشخص کند. اگر فقط یک بیت، n بار علامت بخورد، آن بیت خطا است و با تغییر مقدار آن از 0 به 1 یا برعکس، تصحیح میشود.
-5-3 بیتهای بازفرست
همانگونه که گفته شد، مهمترین ویژگی کد پرسک رخداد حالت بیتهای مشکوک و باز فرست در هنگامی است که روش قادر بهتصحیح خطا نیست. این کار در عمل موجب خواهد شد تا دستگاه بهجای ارسال مجدد کل بسته داده، تنها نیاز به باز فرستادن بیتهای معدودی داشته باشد. این مساله در هنگامی رخ میدهد که جدول درستی بیش از یک بیت را n بار علامت بزند و این موضوع، حل مساله را در وضعیتی غیرقطعی قرار میدهد، اما فضایی جدید را نیز برای آن فراهم میآورد. برای نمونه در یک بسته 2 کیلوبیتی ممکن است 4 بیت n مرتبه علامت بخورد - مشکوک قلمداد شوند - و در این حالت الگوریتم بهدرستی درنمییابد که کدام یک از این 4 بیت خطاست و نیاز به ارسال دوباره آنها دارد، اما باز فرستادن این 4 بیت - حتی همراه با اطلاعات جانبی مورد نیاز - در برابر ارسال کل داده ناچیز است.
