Агуулгыг алгасах

Грэй код

Грэй код бол дараалсан хоёр утга нь зөвхөн нэг битээр ялгаатай байдаг хоёртын тооллын систем юм.

$n$ тоог Грэй кодоор илэрхийлснийг $G(n)$ гэж тэмдэглэе. 3 битийн тооны Грэй кодын дараалал нь: 000, 001, 011, 010, 110, 111, 101, 100, тиймээс $G(4) = (110)_2 = 6$. Жишээ нь $G(3) = (010)_2$ ба $G(4) = (110)_2$ нь яг нэг битээр буюу зүүн талын битээр ялгаатай. Үүнтэй адилаар $G(4) = 110$ ба $G(5) = (111)_2$ нь яг нэг битээр буюу баруун талын битээр ялгаатай. Энэ нь бүх дараалсан тоонуудын хувьд үнэн.

Энэ кодыг Фрэнк Грэй 1953 онд зохион бүтээсэн.

Грэй код олох

$n$ тооны битүүд ба $G(n)$ тооны битүүдийг харцгаая. $G(n)$-ийн $i$ дугаар бит нь зөвхөн $n$-ийн $i$ дугаар бит 1 ба $i + 1$ дугаар бит 0 байх үед, эсвэл эсрэгээрээ ($i$ дугаар бит 0 ба $i + 1$ дугаар бит 1) үед 1-тэй тэнцүү болохыг анзаараарай. Тиймээс $G(n) = n \oplus (n >> 1)$:

int g (int n) {
    return n ^ (n >> 1);
}

Урвуу Грэй код олох

Грэй код $g$ өгөгдсөн үед анхны тоо $n$-г сэргээ.

Бид хамгийн их ач холбогдолтой битээс хамгийн бага ач холбогдолтой бит рүү шилжинэ (хамгийн бага ач холбогдолтой бит нь 1 индекстэй, хамгийн их ач холбогдолтой бит нь $k$ индекстэй). $n$ тооны битүүд $n_i$ ба $g$ тооны битүүд $g_i$ хоорондын хамаарал:

$$\begin{align} n_k &= g_k, \\ n_{k-1} &= g_{k-1} \oplus n_k = g_k \oplus g_{k-1}, \\ n_{k-2} &= g_{k-2} \oplus n_{k-1} = g_k \oplus g_{k-1} \oplus g_{k-2}, \\ n_{k-3} &= g_{k-3} \oplus n_{k-2} = g_k \oplus g_{k-1} \oplus g_{k-2} \oplus g_{k-3}, \vdots \end{align}$$

The easiest way to write it in code is:

int rev_g (int g) {
  int n = 0;
  for (; g; g >>= 1)
    n ^= g;
  return n;
}

Практик хэрэглээ

Грэй код нь заримдаа нэлээд гэнэтийн хэрэгтэй хэрэглээтэй байдаг:

  • $n$ битийн Грэй код нь гиперкуб дээр Гамильтоны цикл үүсгэдэг бөгөөд бит бүр нэг хэмжээст харгалзана.

  • Грэй кодыг тоон-аналог дохионы хувиргалтын алдааг багасгахад (жишээ нь мэдрэгчид) ашигладаг.

  • Грэй кодыг Ханойн цамхагийн бодлого бодоход ашиглаж болно. $n$ нь дискний тоог илэрхийлэг. Бүгд тэгээс бүрдсэн $n$ урттай Грэй кодоос ($G(0)$) эхэлж, дараалсан Грэй кодуудын хооронд шилжинэ ($G(i)$-ээс $G(i+1)$ рүү). Одоогийн Грэй кодын $i$ дугаар бит нь $n$ дугаар дискийг илэрхийлэг (хамгийн бага ач холбогдолтой бит нь хамгийн жижиг дискт, хамгийн их ач холбогдолтой бит нь хамгийн том дискт харгалзана). Алхам бүрт яг нэг бит өөрчлөгддөг тул $i$ дугаар битийг өөрчлөхийг $i$ дугаар дискийг зөөх мэтээр авч үзэж болно. Алхам бүрт (эхлэл ба төгсгөлийн байрлалаас бусад) диск бүрийн хувьд (хамгийн жижгээс бусад) яг нэг зөөх сонголт байдгийг анзаараарай. Хамгийн жижиг дискийн хувьд үргэлж хоёр зөөх сонголт байдаг ч үргэлж хариу руу хөтөлдөг стратеги бий: хэрэв $n$ сондгой бол хамгийн жижиг дискийн хөдөлгөөний дараалал $f \to t \to r \to f \to t \to r \to ...$ хэлбэртэй байна (энд $f$ нь эхлэлийн шон, $t$ нь төгсгөлийн шон, $r$ нь үлдсэн шон), мөн хэрэв $n$ тэгш бол: $f \to r \to t \to f \to r \to t \to ...$.

  • Грэй кодыг мөн генетик алгоритмын онолд ашигладаг.

Дасгал бодлогууд