پاورپوینت کدهای چرخشی

1
کدهای چرخشی
درس پنجم
4001
4002
4000

2
مقدمه
4011
4010
4012
همانطور که می دانیم این احتمال وجود دارد که داده ها در هنگام انتقال با خطا (به ویژه خطای Burst) مواجه شوند. در این فصل کدهای چرخشی را که یکی از رایج ترین روش های کدگذاری برای این موارد است را بررسی می کنیم.

3
5301
روشهای کدینگ
کدهای چرخشی (Cyclic)
5300
5302
5303
کدهای چرخشی یک دسته مهم و پر کاربرد از کد ها هستند. از این نوع کدها بصورت گسترده در سیستمهای ذخیره سازی داده ها (Data storage) و انتقال داده ها (Data Communication) استفاده می شود.
این کدها معمولا بصورت جدا ناپذیر (Non-Separable) هستند ولی با این حال کدهای چرخشی جدا پذیر هم وجود دارد.

4
4391
روشهای کدینگ
کدهای Cyclic (چرخشی)
4390
4392
4393
عمل Decoding با تقسیم داده کد شده به همان عدد ثابت بدست می آید.
اصول کلی این کدها ساده است. عمل کد گذاری (Encoding) به وسیله ضرب کردن داده در یک عدد ثابت انجام می شود.
عمل ضرب از نوع پیمانه 2 (Modulo-2) می باشد.
اگر باقیمانده تقسیم صفر نشود، نشان دهنده آن است که یک خطا وجود دارد.
(فرض کنیم که هر کلمه از داده ها داراى طول D باشد).
4394
4395

5
4401
روشهای کدینگ
کدهای Cyclic (چرخشی)
4400
4402
4403
N طول نهائی عدد کد شده است.
حال بیایید نگاه دقیق ترى به این روش بیندازیم.
فرض کنید K تعداد بیت هاى داده ای باشد که می خواهیم آن را کد کنیم.
این عدد کد شده از ضرب K بیت اولیه در یک عدد ثابت که طول آن N-K+1 است، به دست می آید.
این عدد ثابت را می توانیم به صورت یک چند جمله ای نشان دهیم که اصطلاحا به آن چند جمله ای مولد (Generator Polynomial) می گویند که در آن 1 ها و 0 های عدد ثابت N-K+1 بیتی به عنوان ضرایب چند جمله ای با درجه N-K می باشد.
4404
4405
4406

6
4411
روشهای کدینگ
کدهای Cyclic (چرخشی)
4410
4412
4413
G(X) = 1 X0 + 0 X1 + 0 X2 + 1 X3 + 1 X4
= X0 + X3 + X4
برای روشن تر شدن موضوع به مثال زیر توجه کنید:
فرض کنید عدد ثابت مورد نظر 11001 باشد، در نتیجه چند جمله ای مولد برابر است با:
4414

7
4421
روشهای کدینگ
کدهای Cyclic (چرخشی)
4420
4422
4423
یک کد (n, k) می تواند هر نوع خطای تک بیتی را تشخیص دهد.
کد چرخشی (n, k)
کد چرخشی (n, k) از یک چند جمله ای مولد از درجه n-k استفاده می کند و طول داده کد شده آن n بیت خواهد بود.
همچنین می تواند هر نوع خطا در n-k بیت مجاور را تشخیص دهد.
حسن این سیستم این است که می تواند خطاهای Burst را تشخیص دهد.
4424
4425
4426

8
4431
روشهای کدینگ
کدهای Cyclic (چرخشی)
4430
4432
4433
پیاده سازى سخت افزاری
برای آنکه سخت افزار تولید کننده این کد را بسازیم از Shift Register و XOR برای سخت ضرب کننده استفاده می کنیم.
برای مثال فرض کنید که می خواهیم چند جمله ای 1 + X3 + X4 را پیاده سازی کنیم (11001). مدار Encoding (کد گذاری) به صورت زیر است:
4434
4435

9
4441
روشهای کدینگ
کدهای Cyclic (چرخشی)
4440
4442
4443
عناصری که با D نشان داده شده اند در واقع همانند Filp-Flop های نوع D هستند که اطلاعات را در هر Clock در خود نگه می دارند به این بلوک ها عناصر تاخیر هم می گویند.
حال ببینیم این مدار چگونه کار می کند.
همانطور که می دانیم عمل ضرب چه در سیستمهای دهدهی و چه در سیستم دودویی به این شکل است که هر رقم عدد دوم در عدد اول ضرب می شود و نتیجه هر بار یک رقم جابجا (Shift Right) می شود و در نهایت کل آنها با هم جمع می شوند.
4444

10
4451
روشهای کدینگ
کدهای Cyclic (چرخشی)
4450
4452
4453
این عمل در مورد مثال ما در شکل روبرو مشخص است.
در این شکل عدد ورودی 1100101 در نظر گرفته شده است. در مدار ما عمل جمع یک بیت به صورت Modulo-2 است که با کمک یک XOR قابل انجام است.
4454

11
4461
روشهای کدینگ
کدهای Cyclic (چرخشی)
4460
4462
4463
در این مدار عمل ضرب و جمع تواما انجام می شود.
به این شکل که رشته ورودی به صورت بیت به بیت وارد می شود.
بیت اول به طور هم زمان به سه قسمت مدار وارد می شود.
در سمت راست بیت ورودی مستقیما وارد XOR می شود، در نتیجه بدون هیچ تغییر یا تاخیر در خروجى تاثیر می کند.
در لحظه اول تمام Filp-Flip ها 0 هستند.
4464
4465
4466

12
4471
روشهای کدینگ
کدهای Cyclic (چرخشی)
4470
4472
4473
اما در قسمت وسط بیت وارد شده به اندازه سه Clock دیرتر به خروجى می رسد، زیرا در سر راه آن سه Flip-Flip قرار دارد.
پس عملا در زمانى که بیت چهارم وارد سیستم می شود، تازه بیت اول از این مسیر به خروجى می رسد.
به دنبال بیت اول سایر بیت ها هم با سه Clock تاخیر به خروجى می رسند.
بعبارتی می توان گفت همه آنها به اندازه 3 بیت شیفت پیدا کرده اند، یعنی همان چیزی که ما می خواستیم.
4474
4475

13
4481
روشهای کدینگ
کدهای Cyclic (چرخشی)
4480
4482
4483
پس عملا ورودی ها در سه جای مختلف با 0 بار تاخیر، 3 بار تاخیر و 4 بار تاخیر به خروجى می روند و باهم جمع می شوند که معادل 1 + X3 + X4 می باشد.
شکل زیر مراحل این عمل را نشان میدهد.
در سمت چپ نیز بیت ورودی با یک تاخیر اضافه نسبت به حالت قبل با چهار Clock تاخیر روی خروجى تاثیر می گذارد.
4484

14
4491
روشهای کدینگ
کدهای چرخشی
4490
4492
شکل زیر مراحل این عمل را نشان میدهد.
I3 به عنوان ورودی
Flip-Flop O3است.
4493
4494
4495

15
4501
روشهای کدینگ
کدهای Cyclic (چرخشی)
4500
4502
4503
نتیجه این کد برای مثال ما به صورت 10100011101 است که خود نشان دهنده همین واقعیت است.
این نوع کد چرخشی به صورت جدا ناپذیر (Non Separable) است.

16
4511
کدهای Cyclic (چرخشی)
کد گشایی (Decoding)
4510
4512
4513
برای اینکه عمل Decoding را انجام دهیم، باید رشته ورودی را به چند جمله ای مولد تقسیم کنیم.
مسئله مهم در اینجا اینست که سیستم بتواند خطاها را تشخیص دهد.
اگر یک خطای تک بیت داشته باشیم، کاملا مشخص است که باقیمانده تقسیم 0 نخواهد بود.
4514

17
4521
کدهای Cyclic (چرخشی)
کد گشایی (Decoding)
4520
4522
4523
در شکل زیر (سمت چپ) این محاسبات انجام شده است و همان طور که می بینیم نتیجه آن با ورودی اولیه یکی است. ولی در سمت راست یک بیت خطا دارد و باقیمانده صفر نیست.

18
4531
کدهای Cyclic (چرخشی)
کد گشایی (Decoding)
4530
4532
4533
حال فرض کنید خطا در 3 بیت باشد، در این صورت 2 حالت وجود دارد: یکی اینکه هر 3 بیت کنار هم باشند (Adjacent) و دیگر اینکه از هم جدا باشند.
در مثال زیر این دو حالت نشان داده شده است.
همان طور که می بینیم وقتی سه بیت خطا کنار هم نیستند این احتمال وجود دارد که خطا کشف (Detect) نشود.
ولی وقتی سه بیت خطا کنار هم هستند، خطا حتما تشخیص داده می شود. در اینجا فرقی نمی کند که خطا تبدیل 0 به 1 یا 1 به 0 یا حتی ترکیبى از هردوی آنها باشد. می توانید به عنوان تمرین این موضوع را خودتان بررسی کنید.
4534
4535

19
4541
کدهای Cyclic (چرخشی)
پیاده سازى مدار تقسیم کننده
4540
4542
4543
برای مثال فرض کنید چند جمله ای دریافت شده را با E(X) نشان دهیم و چند جمله ای مولد را با G(X) و چند جمله ای اصلی (داده اصلی) را با D(X) نشان دهیم.
در این حالت اگر هیچ نوع خطایی وجود نداشته باشد (باقیمانده صفر باشد) بعد از آنکه E(X) را دریافت کردیم، آن را به G(X) تقسیم می کنیم تا D(X) به دست آید.
یعنی داریم:
D(X) = E(X)/G(X)
برای آنکه مدار تقسیم کننده را بسازیم می توانیم از Feedback در مدار ضرب کننده استفاده کنیم.
4544
4545
4546

20
4551
کدهای Cyclic (چرخشی)
پیاده سازى مدار تقسیم کننده
4550
4552
4553
حال فرض کنید G(X) = 1 + X3 + X4 باشد.
پس داریم :
E(X) = D(X)G(X) = D(X)(1+X3+X4) = D(X) + D(X)(X3 + X4)
و در نتیجه:
D(X) = E(X) – D(X)(X3 + X4) = E(X) + D(X)(X3 + X4)
در رابطه بالا علامت تفریق را با علامت جمع عوض کردیم. علت این کار اینست که تفریق پیمانه 2 (Modulo-2) با جمع آن معادل است.
4554
4555
4556

21
4561
کدهای Cyclic (چرخشی)
پیاده سازى مدار تقسیم کننده
4560
4562
4563
حال بر همین اساس مدار را طراحی می کنیم.
مدار ما باید ورودی ( E(X) ) را با D(X)(X3 + X4) جمع کند و دوباره کل آن را به عنوان D(X) به مدار بر گرداند (Feed Back).
4564

22
4571
کدهای Cyclic (چرخشی)
پیاده سازى مدار تقسیم کننده
4570
4572
4573
در مدار بالا تمامی Flip-Flop ها در ابتدای کار مقدار 0 را دارند.
وقتی اطلاعات وارد مدار می شود، خروجى آن به صورت بیت به بیت تولید می شود که 7 بیت اول آن داده های اصلی هستند و 4 بیت بعدی آن باقیمانده است که باید 0 باشد.
اگر باقی مانده 0 نبود، نشان دهنده این است که یک خطا روى داده است.
شکل و جدول زیر اطلاعات را در هر مرحله نشان میدهد.
4574
4575

23
4581
کدهای Cyclic (چرخشی)
پیاده سازى مدار تقسیم کننده
4580
4582
4583
شکل و جدول زیر اطلاعات را در هر مرحله نشان میدهد.
I3 ورودی Flip-Flop O3 است که برابر I4+O4 می باشد
4584

24
4591
روشهای کدینگ
کدهای Cyclic (چرخشی)
4590
4592
4593
در کدهای چرخشی (N, K) تعداد بیت های افزونه (N-K) به تعداد بیت هاى داده (K) وابسته نیست.
عدد K می تواند بزرگ شود بدون آنکه N-K(درجه چند جمله ای مولد) افزایش یابد یا آنکه پیچیدگی مدار Encoding و Decoding بیشتر شود.

25
4601
کدهای Cyclic (چرخشی)
تشخیص خطاهای Burst
4600
4602
4603
خطای Burst خطایی است که بصورت پشت سر هم یک مجموعه از بیت ها را از بین می برد.
همان طور که گفتیم یکی از مزیت های کد های چرخشی این است که می توانند این نوع خطا ها را تشخیص دهند.
این روش تنها خطاهائی را که طول آنها از N-K کمتر باشد، تضمین می کند که بتواند تشخیص دهد.
با بزرگ شدن K (طول داده اصلی) قابلیت کد برای تشخیص خطاهای Burst کم می شود.
4603
4604

26
4611
کدهای Cyclic (چرخشی)
تشخیص خطاهای Burst
4610
4612
4613
در بسیاری از کاربردها لازم است که تضمینی وجود داشته باشد که تمامی خطاهائی که طول آنها برابر 16 بیت یا کمتر است، قابل تشخیص باشند.
در این حالت از کد چرخشی (k+16, k) استفاده می شود.

27
4621
روشهای کدینگ
کدهای Cyclic (چرخشی)
4620
4622
4623
G(X) = X16 + X15 + X2 + 1
پرکاربرد ترین این کدها اصطلاحا
CRC-16 (16-Bit Cyclic Redundancy Code) گفته می شود که چند جمله ای مولد آن به صورت زیر است:
G(X) = X16 + X12 + X5 + 1
همچنین CRC-CCITT که چند جمله ای مولد آن به صورت زیر است، یکی از کدهای معروف می باشد.
4624
4625