UK 
EnglishТипова
Polski🔢 Код Грея — віддзеркалений двійковий та шлях на гіперкубі
Досліджуйте код Грея (g = b XOR b>>1), де кожне наступне значення змінює один біт. Крокуйте послідовністю 2ⁿ, простежте гамільтонів шлях на n-кубі й побачте, чому енкодери уникають багатобітних помилок.
Схожі симуляції
Про код Грея
Код Грея (формально — двійковий віддзеркалений код Грея, BRGC) — це впорядкування двійкових чисел, у якому сусідні значення відрізняються рівно одним бітом. Винайдений Френком Греєм у Bell Labs 1947 року й запатентований для використання в імпульсно-кодовій модуляції, він усуває перехідні багатобітні помилки, що виникають у звичайній двійковій системі, коли кілька бітів змінюються одночасно — це критично важливо в цифровій електроніці, де сигнали не можуть змінюватися миттєво. Поворотні енкодери валу, аналого-цифрові перетворювачі та карти Карно використовують властивість зміни лише одного біта, щоб зменшити помилки-збої та спростити мінімізацію логіки.
Ця симуляція візуалізує коди Грея як шлях на n-вимірному гіперкубі: кожна бітова позиція відповідає одній осі, а кожен перехід коду Грея — це ребро куба. Ви можете покроково проходити послідовність для n від 1 до 5, спостерігаючи, як обхід відвідує кожну вершину рівно один раз — гамільтонів шлях на графі гіперкуба — і бачити, як кожен перехід змінює рівно один біт.
Часті запитання
Як будується стандартний код Грея з двійкового числа?
n-бітовий код Грея G(k) для цілого числа k обчислюється як G(k) = k XOR (k >> 1): беремо двійкове представлення k, зсуваємо його на одну позицію вправо і виконуємо XOR з оригіналом. Наприклад, k=6 (двійкове 110) → 110 XOR 011 = 101 (десяткове 5), що дає 4-й код Грея в 3-бітовій послідовності (0,1,3,2,6,7,5,4 у десятковій системі). Зворотна операція — відновлення k з G(k) — вимагає ітеративного префіксного XOR по всіх бітах.
Чому код Грея важливий для поворотних енкодерів?
Поворотний енкодер зчитує кутове положення валу за патерном відбивних або провідних сегментів. Якщо використовується стандартна двійкова система, перехід типу 7→8 (0111→1000) вимагає зміни всіх чотирьох бітів; якщо механічне зчитування трохи розсинхронізується, можуть бути прочитані проміжні стани на кшталт 0110 чи 1010, що дасть зовсім неправильні позиції. Код Грея гарантує, що сусідні позиції завжди відрізняються рівно одним сегментом, тож у невизначеному стані може перебувати лише один біт, обмежуючи похибку позиції до ±1.
Що таке «віддзеркалена» побудова, яка дала коду Грея повну назву?
n-бітовий BRGC будується рекурсивно: беремо список (n−1)-бітових кодів Грея, додаємо до кожного префікс 0, отримуючи перші 2n−1 записів, а потім додаємо перевернутий список із префіксом 1. «Віддзеркалення» стосується саме цього дзеркального перевертання, яке гарантує, що останній запис половини з префіксом 0 і перший запис половини з префіксом 1 відрізняються рівно одним бітом (старшим). Ця рекурсія дає той самий результат, що й формула XOR G(k) = k XOR (k >> 1).
Як код Грея використовується в картах Карно?
Карти Карно розташовують клітинки таблиці істинності в порядку коду Грея вздовж кожної осі, щоб логічно сусідні мінтерми (що відрізняються в одній змінній) були фізично сусідніми в сітці. Це дозволяє візуально виявляти прямокутники з одиниць (або нулів), що відповідають простим імплікантам, спрощуючи булеві вирази. Без упорядкування за Греєм сусідні клітинки сітки не були б логічно сусідніми, що зводило б нанівець сенс карти.
Чи є послідовність коду Грея унікальною?
Ні. Для n бітів існує багато різних послідовностей зі зміною одного біта; їх називають кодами Грея або гамільтоновими циклами на n-кубі, і їхня кількість зростає супер-експоненційно з n. Двійковий віддзеркалений код Грея є канонічним вибором завдяки простій рекурсивній побудові та формулі XOR у замкненому вигляді. До інших родин належать збалансовані коди Грея (де кожен біт змінюється приблизно однаково часто), монотонні коди Грея та коди «змія в коробці» (Snake-in-the-Box), що використовуються для виправлення помилок.
Як код Грея пов'язаний з Ханойською вежею?
Послідовність бітових позицій, що змінюються в послідовних значеннях коду Грея, точно збігається з послідовністю номерів дисків, які рухаються в оптимальному розв'язку Ханойської вежі: позиція 1, 2, 1, 3, 1, 2, 1, 4, … («лінійкова» послідовність). Цей ізоморфізм означає, що кожен хід у головоломці Ханой відповідає зміні одного біта в лічильнику коду Грея, що дає глибокий комбінаторний зв'язок між цими двома задачами.
Що таке збалансований код Грея?
Збалансований код Грея — це такий код, у якому кожна бітова позиція змінюється майже однаково часто серед усіх 2n переходів. У стандартному BRGC старший біт змінюється лише раз, тоді як молодший біт змінюється 2n−1 разів, що дає дуже нерівномірний розподіл. Збалансовані коди Грея розподіляють переходи рівномірно, що важливо в таких застосуваннях, як вирівнювання зносу флеш-пам'яті та зменшення потужності перемикання в схемах КМОН.
Як код Грея використовується для виправлення помилок?
Коди «змія в коробці» (Snake-in-the-Box) — це шляхи коду Грея на n-кубі, де жодні дві несуміжні вершини шляху не є суміжними в кубі (гамільтонів шлях, що «звивається»). Вони утворюють коди із самовиявленням одиничної помилки: будь-яка одиночна бітова помилка в кодовому слові переводить його у вершину, що не є кодовим словом. Коди «котушка в коробці» (Coil-in-the-Box) досягають більшої мінімальної відстані Гемінга. Ці комбінаторні коди застосовуються у відмовостійких обчисленнях і системах зберігання даних.
Чи можна визначити коди Грея для недвійкових систем числення?
Так. Існують збалансовані трійкові коди Грея, коди Грея зі змішаною основою та коди Грея для перестановок. Алгоритм Штейнгауза–Джонсона–Троттера генерує всі перестановки N елементів суміжними транспозиціями, що є аналогом коду Грея зі зміною одного елемента для перестановок. Вони використовуються в алгоритмах повного перебору, що перелічують перестановки чи комбінації з мінімальною зміною між послідовними станами.
Як код Грея спрощує проєктування цифрових схем?
У послідовних автоматах станів (FSM) кодування станів кодом Грея гарантує, що для переходу між станами потрібно змінити лише один тригер за раз. Це усуває перехідні збійні стани, які могли б викликати небажану логіку, зменшуючи споживання енергії й покращуючи запаси часу. Інструменти проєктування FPGA часто автоматично пропонують кодування FSM кодом Грея як опцію, коли розробник обирає стилі кодування «безпечний» або «one-hot-adjacent».
Про цю симуляцію
Ця симуляція будує двійковий віддзеркалений код Грея для обраної кількості бітів і анімує його як обхід n-вимірного гіперкуба. Кожне ціле число перетворюється за формулою g = b XOR (b >> 1), тож послідовні коди завжди відрізняються одним бітом. Обхід є гамільтоновим шляхом; другий режим відображає його на диску поворотного енкодера, третій — у вигляді таблиці.
Що насправді показують три режими перегляду (Гіперкуб, Енкодер, Таблиця)?
Режим «Гіперкуб» малює вершини й ребра куба та простежує гамільтонів шлях у міру просування послідовності. Режим «Енкодер» відображає ті самі коди у вигляді концентричних кілець на диску, як у справжньому поворотному енкодері. Режим «Таблиця» перелічує двійкові коди й коди Грея поряд.
Що означає статистика «змінений біт»?
Вона показує, яка бітова позиція змінилася між попереднім і поточним кодом Грея, рахуючи від старшого біта. До першого кроку показується риска, а потім — індекс на кшталт #0 або #1 — завжди рівно один біт.
Чому розташування гіперкуба змінюється при русі повзунка кількості бітів n?
Кожен біт додає одну вісь: 2 біти утворюють квадрат, 3 біти — куб, а до 4 бітів включно проєкція сплющується з фіксованим напрямком для кожного біта. Понад 4 біти розташування переходить у коло, рівномірно розподіляючи всі 2n кодів, оскільки плоска проєкція стає нечитабельною.
Що таке концентричні кільця в режимі «Енкодер»?
Кожне кільце представляє один біт, причому найзовнішнє кільце — найстарший біт. Сегмент засвічується щоразу, коли цей біт дорівнює 1 для коду при цьому куті, тож диск відтворює патерн, який справжній абсолютний поворотний енкодер друкує на своєму кодовому диску.
Чим відрізняються керування «Відтворити», «Крок» і «Скинути»?
«Відтворити» відтворює анімацію безперервно зі швидкістю, заданою повзунком Швидкість, просуваючись на одне ребро за раз до кінцевого коду. «Крок» просуває рівно на один код і зупиняється. «Скинути» повертає послідовність до індексу 0 і зупиняє будь-яку активну анімацію.