Код Грея - EcsFlash/DataTypes GitHub Wiki

Код Гре́я — двоичный код, иначе зеркальный код, он же код с отражением, в котором две «соседние» (в упорядоченном, то есть лексикографическом, наборе) кодовые комбинации различаются только цифрой в одном двоичном разряде. Иными словами, расстояние Хэмминга между соседними кодовыми комбинациями равно 1.

Наиболее часто на практике применяется рефлексивный двоичный код Грея, хотя в общем случае существует бесконечное множество кодов Грея со значениями цифр в разрядах, взятых из различных алфавитов. В большинстве случаев, под термином «код Грея» понимают именно рефлексивный бинарный код Грея.

Изначально предназначался для защиты от ложного срабатывания электромеханических переключателей. Сегодня коды Грея широко используются для упрощения выявления и исправления ошибок в системах связи, а также в формировании сигналов обратной связи в системах управления. Крч какая то бесполезная шляпа.

Как генерировать коды грея

Выписываете 0 и 1 в столбик, отражаете по горизонтали, в верхней половине в старший разряд приписываете 0, в нижней - 1, затем отражаете всю эту шляпу по горизонтали и погнали всё по новой.

Как это делается в коде:

Псевдокод

func grayCode(n int) []int {
	return recur(n, 1, []int{0})
}

func recur(n, base int, nums []int) []int {
	if n == 0 {
		return nums
	}
	var temp []int
	for i := range nums {
		temp = append(temp, nums[len(nums)-i-1]+base)
	}
	return recur(n-1, base*2, append(nums, temp...))
}

Статистика

┌────────────┬────────────────┬──────────────────┬────────────────┐
│ Сложность  │ Лучший случай  │ Средний случай   │ Худший случай  │
├────────────┼────────────────┼──────────────────┼────────────────┤
│   Время    │     O(2ⁿ)      │      O(2ⁿ)       │     O(2ⁿ)      │
├────────────┼────────────────┼──────────────────┼────────────────┤
│  Память    │     O(2ⁿ)      │      O(2ⁿ)       │     O(2ⁿ)      │
└────────────┴────────────────┴──────────────────┴────────────────┘