«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan kurs ishi

N-bitli Grey kodini yaratishn-bitli Grey kodni quyidagicha izohlash va aks ettirish (prefiks) usuli yordamida rekursiv ravishda yaratish mumkin.

• 
  N = 1: 0 va 1 kodlari uchun kod yarating.
  
• 
  Oldingi kodni ketma-ketlikda oling: 0 va 1.
  
• 
  Quyidagi ro’yxatga teskari kodlarni qo’shing: 0, 1, 1 va 0.
  

Endi avvalgi dastlabki kod uchun 0 prefiksini va yangi yaratilgan kod uchun 1-prefiksni qo’shing: 00, 01, 11 va 10.

Shuning uchun Gray kodi 0 va 1 mos ravishda Ikkilik raqamlar 0 va 1 uchun. Kulrang kodlar: 00. 01, 11 va 10 ikkilik raqamlar uchun mos ravishda 00, 01, 10 va 11. Xuddi shu tarzda siz 3 bitli ikkilik raqamlar uchun Grey kodini yaratishingiz mumkin:

Shuning uchun Grey kodlari quyidagicha,

Gn dan G (n + 1) hosil qilishning takroriy usuli quyida keltirilgan. Bu n-bit Ikkilik raqamlarning kulrang kodini qisqartirish uchun oddiy usul. Kirish qiymatining keyingi yuqori biti bittaga o’rnatilgan bo’lsa, har bir bit teskari bo’ladi. N-Grey kodi n comp (qavat (n / 2)) hisoblash orqali olinadi.

• 
  Gn - 0 dan (2n-1) gacha bo’lgan permutatsiya uchun noyob sonlar.
  
• 
  Gn G (n + 1) ning birinchi yarmi, ikkinchi yarmi esa G (n + 1) ning teskari tartibi sifatida joylashtirilgan.
  
• 
  Birinchi yarmning har bir raqamida 0 prefiksi va ikkinchi yarmining har bir raqamida 1.
  

Ikkala qo’shnining tortishish masofasi har doim 1 ga teng, shuningdek birinchi Grey kodi va oxirgi Grey kodi ham Hamming masofasi har doim 1 ga teng, shuning uchun uni Tsiklik kodlar ham deyishadi. Siz Grey kodlarini boshqa usullardan foydalangan holda tuzishingiz mumkin, ammo ular yuqorida ko’rsatilgan usulga o’xshash parallel ravishda bajarilmasligi mumkin. Masalan, 3 bitli Grey kodlari bilan quyidagicha berilgan K-map yordamida shartnoma tuzish mumkin: