Выпишем 25 записей таблицы (см здесь) в трёх системах счисления (десятичный, hex и двоичный), причём в двоичной записи в тех местах, где "без разницы" (don't care), вместо нуля или единицы ставим буковку x. Вот что выходит:
93 = 0x005D = xxxx_xxxx_0101_1101 24 = 0x0018 = xxxx_xxxx_0001_1000 0 = 0x0000 = 0000_0000_0000_0000 3 = 0x0003 = xxxx_xxxx_xxx0_0011 1 = 0x0001 = 0000_0000_0000_0001 25 = 0x0019 = xxxx_xxxx_xxx1_1001 23 = 0x0017 = xxxx_xxxx_xxx1_0111 240 = 0x00F0 = xxxx_xxxx_1111_0000 26 = 0x001A = xxxx_xxxx_0001_1010 28 = 0x001C = xxxx_xxxx_0001_1100 30 = 0x001E = xxxx_xxxx_0001_1110 49 = 0x0031 = xxxx_xxxx_0011_0001 199 = 0x00C7 = xxxx_xxxx_1100_0111 11010 = 0x2B02 = 0010_1011_0000_0010 22 = 0x0016 = xxxx_xxxx_xxx1_0110 242 = 0x00F2 = xxxx_xxxx_1111_0010 16384 = 0x4000 = 0100_0000_0000_0000 205 = 0x00CD = xxxx_xxxx_1100_1101 -13 = 0xFFF3 = xxxx_xxxx_xxx1_0011 27 = 0x001B = xxxx_xxxx_xxx1_1011 238 = 0x00EE = xxxx_xxxx_1110_1110 203 = 0x00CB = xxxx_xxxx_1100_1011 236 = 0x00EC = xxxx_xxxx_1110_1100 43648 = 0xAA80 = 1010_1010_1000_0000 21758 = 0x54FE = 0101_0100_1111_1110
Поехали!
Начинаем с самого младшего разряда. Подсчитываем, сколько раз нам нужен нолик: 14 раз. И единичка нужна 11 раз. Нас устраивает не более 64 того и другого, так что можно младший разряд "таблицы" присоединить напрямую к младшему биту адреса SrcAddr[0]:
assign Q[0] = SrcAddr[0];
И все наши значения теперь разделяются на две группы:
Группа 0 (оканчивается на 0): 24, 0, 240, 26, 28, 30, 11010, 22, 242, 16384, 238, 236, 43648, 21758 Группа 1 (оканчивается на 1): 93, 3, 1, 25, 23, 49, 199, 205, -13, 27, 203
И ещё запоминаем "сигнатуру" - это последовательность младших бит, прочитанная сверху вниз по этой таблице: 1001_1110_0001_1000_0111_0100_0
Принимаемся за следующий бит, второй с конца. У него сигнатура:
0001_0010_1010_1111_0011_1100_1
Она не совпадает со "всеми нулями", не совпадает со "всеми единицами" и не совпадает с сигнатурой самого младшего разряда, значит, "схитрить" не удастся (скоммутировать выход на ноль, на единицу или на самый младший разряд). Попробуем его напрямую "скоммутировать" на следующий бит адреса SrcAddr[1]:
assign Q[1] = SrcAddr[1];
Это разделяет наши команды на 4 группы:
Группа 0 (оканчивается на 00): 24, 0, 240, 28, 16384, 236, 43648 (7 значений) Группа 1 (оканчивается на 10): 26, 30, 11010, 22, 242, 238, 21758 (7 значений) Группа 2 (оканчивается на 01): 93, 1, 25, 49, 205 (5 значений) Группа 3 (оканчивается на 11): 3, 23, 199, -13, 27, 203 (6 значений)
В каждую из них должно попасть не более 32 значений - так и есть, значит, всё в порядке.
Принимаемся за следующий бит, 3-й с конца. Сигнатура: 1000_0010_0110_1010_0100_1010_1, не совпадает со "всеми нулями", "всеми единицами" и сигнатурами предыдущих бит. Значит, и этот бит надо кодировать "честно". Попробуем на него выделить очередной бит адреса:
assign Q[2] = SrcAddr[2];
И теперь наши значения разделяются на 8 групп:
Группа 0 (оканчивается на 000): 24, 0, 240, 16384, 43648 (5 значений) Группа 1 (оканчивается на 100): 28, 236 (2 значения) Группа 2 (оканчивается на 010): 26, 11010, 242 (3 значения) Группа 3 (оканчивается на 110): 30, 22, 238, 21758 (4 значения) Группа 4 (оканчивается на 001): 1, 25, 49 (3 значения) Группа 5 (оканчивается на 101): 93, 205 (2 значения) Группа 6 (оканчивается на 011): 3, -13, 27, 203 (4 значения) Группа 7 (оканчивается на 111): 23, 199 (2 значения)
В каждой группе должно быть не более 16 значений - так и есть. Мы просто боимся, что если в каком-то разряде будет большой "разбаланс" между нулями и единицами, то потом оставшихся битов SrcAddr не хватит, чтобы отличить значения друг от друга. Пока у нас всё ровно.
Берёмся за следующий бит, 4-й с конца
Сигнатура 1100_0100_1110_0000_0101_1110_1 - не совпадает с предыдущими, значит и этот бит надо кодировать "самостоятельно". Попробуем его напрямую "скоммутировать" на очередной бит адреса, благо, они у нас пока есть:
assign Q[3] = SrcAddr[3];
И тем самым разбиваем наши значения на 16 групп:
Группа 0 (оканчивается на 0000): 0, 240, 16384, 43648 (4 значения) Группа 1 (оканчивается на 1000): 24 (1 значение) Группа 2 (оканчивается на 0100): (пусто) Группа 3 (оканчивается на 1100): 28, 236 (2 значения) Группа 4 (оканчивается на 0010): 11010, 242 (2 значения) Группа 5 (оканчивается на 1010): 26 (1 значение) Группа 6 (оканчивается на 0110): 22 (1 значение) Группа 7 (оканчивается на 1110): 30, 238, 21758 (3 значения) Группа 8 (оканчивается на 0001): 1, 49 (2 значения) Группа 9 (оканчивается на 1001): 25 (1 значение) Группа 10 (оканчивается на 0101): (пусто) Группа 11 (оканчивается на 1101): 93, 205 (2 значения) Группа 12 (оканчивается на 0011): 3, -13 (2 значения) Группа 13 (оканчивается на 1011): 27, 203 (2 значения) Группа 14 (оканчивается на 0111): 23, 199 (2 значения) Группа 15 (оканчивается на 1111): (пусто)
В каждой группе должно быть не более 8 значений - так оно и есть.
Принимаемся за очередной бит, 5-й с конца. Сигнатура:
1100_0111_1111_0011_0011_0000_1 - не совпадает с другими, так что и этот бит надо кодировать "самостоятельно":
assign Q[4] = SrcAddr[4];
Теперь все значения делятся на 32 группы, теперь уже существенная их часть: пустые, так как значений всего 25!
Группа 0 (оканчивается на 0_0000): 0, 16384, 43648 (3 значения) Группа 1 (оканчивается на 1_0000): 240 (1 значение) Группа 2 (0_1000): (пусто) Группа 3 (1_1000): 24 (1 значение) Группы 4 (0_0100), 5 (1_0100): (пусто) Группа 6 (0_1100): 236 (1 значение) Группа 7 (1_1100): 28 (1 значение) Группа 8 (0_1100): 11010 (1 значение) Группа 9 (1_1100): 242 (1 значение) Группа 10 (0_1010): (пусто) Группа 11 (1_1010): 26 (1 значение) Группа 12 (0_1010): (пусто) Группа 13 (1_1010): 22 (1 значение) Группа 14 (0_1110): 238 (1 значение) Группа 15 (1_1110): 30, 21758 (2 значения) Группа 16 (0_0001): 1 (1 значение) Группа 17 (1_0001): 49 (1 значение) Группа 18 (0_1001): (пусто) Группа 19 (1_1001): 25 (1 значение) Группы 20 (0_0101), 21 (1_0101): (пусто) Группа 22 (0_1101): 205 (1 значение) Группа 23 (1_1101): 93 (1 значение) Группа 24 (0_0011): 3 (1 значение) Группа 25 (1_0011): -13 (1 значение) Группа 26 (0_1011): 203 (1 значение) Группа 27 (1_1011): 27 (1 значение) Группа 28 (0_0111): 199 (1 значение) Группа 29 (1_0111): 23 (1 значение) Группы 30 (0_1111), 31 (1_1111): (пусто)
В каждой группе может содержаться до 4 значений (у нас осталось ещё 2 бита адреса, которые позволили бы разграничить эти значения), то есть пока всё работает.
Теперь начинаются более старшие биты, где во многих значениях вместо 0 или 1 стоит "don't care" (x)
Обрабатываем 6-й бит с конца.
"Сигнатура" этого бита: 000x_0xx1_0001_00x1_00xx_1010_1. Когда мы будем сравнивать её с другими, на месте "х" нам совпадения не требуется, лишь бы другие совпали. И поначалу кажется, что у нас будет совпадение со 2-м битом с конца:
2-й: 0001_0010_1010_1111_0011_1100_1 6-й: 000x_0xx1_0001_00x1_00xx_1010_1
но уже на 8-м значении они не совпадают. Совпади они - и мы продублировали бы тот же самый бит и на этом месте, и стало бы сразу ясно, что поставить на месте "иксов". Но шансы на такое совпадение довольно малы, всё-таки 2-25 - это очень маленькое число. Тут вероятность повыше, всё-таки и часть битов "запикивается", и сравнивается не с одной строкой, а с 7 строками (5 бит, а ещё "все нули" и "все единицы"), но шансы по-прежнему малы.
А так выходит, что мы должны задействовать ещё один бит адреса, а при разделении на 64 группы понять, куда поместить значения, у которых в этом бите "don't care". Теперь уже в каждой группе может содержаться не более 2 значений, и это может сыграть свою роль.
И тут происходит конфуз! Прямо в новую "нулевую группу" (00_0000) попадает сразу 3 значения:
0 = 0x0000 = 0000_0000_0000_0000, 16384 = 0x4000 = 0100_0000_0000_0000, 43648 = 0xAA80 = 1010_1010_1000_0000
Поэтому сделать такое сопоставление:
assign Q[5] = SrcAddr[5]; //DON'T DO THAT!!!
мы не имеем права! Этот бит должен выражаться некоторой логической функцией от других бит, и мы его пока "отложим".
Обрабатываем 7-й бит с конца
Его "сигнатура": 100x_0xx1_0000_10x1_01xx_1110_1. Опять могло показаться, что пошло совпадение, теперь с 3-м битом с конца:
3-й: 1000_0010_0110_1010_0100_1010_1 7-й: 100x_0xx1_0000_10x1_01xx_1110_1
Но и здесь есть несовпадения. Поэтому предполагаем задействовать ещё один бит адреса:
assign Q[6] = SrcAddr[5];
но только при условии, что у нас "разрешатся" значения, т.е в каждой "группе" будет не более 2 значений. А этого опять не происходит, в том же самом месте:
0 = 0x0000 = 0000_0000_0000_0000, 16384 = 0x4000 = 0100_0000_0000_0000, 43648 = 0xAA80 = 1010_1010_1000_0000
На 7-м бите во всех 3 значениях стоит ноль, а останется лишь один бит адреса, SrcAddr[6], т.к SrcAddr[7] нужен, чтобы выбрать между "непосредственными значениями" (SrcAddr[7]=0) и всеми прочими модулями QuatCore.
Так что и 7-й бит пока придётся отложить!
Рассматриваем 8-й бит с конца
Его сигнатура: 000x_0xx1_0000_10x1_01xx_1111_1
И снова неудача: ни с какой другой она не совпадает, даже если вместо иксов подставить произвольные значения.
Значит, снова попытаемся задействовать бит адреса:
assign Q[7] = SrcAddr[5];
И вот теперь наши злосчастные 3 значения наконец-то удаётся разделить:
Группа 0 (0xx0_0000): 0, 16384 Группа 1 (1xx0_0000): 43648 Группа 2 (0xx1_0000): (пусто) Группа 3 (1xx1_0000): 240 Группы 4 (0xx0_1000), 5 (1xx0_1000): (пусто) Группа 6 (0xx1_1000): 24 Группы 7 (1xx1_1000), 8 (0xx0_0100), 9 (1xx0_0100), 10 (0xx1_0100), 11 (1xx1_0100): (пусто)
А дальше появляются значения "don't care", и их тоже надо как-то распихать. Мы пока встречаем "тривиальный частный случай", когда в группе всего одно значение, и в нём на очередном бите стоит "don't care" (x). Тогда можно поставить что угодно. По-хорошему, нужно каким-то образом это обозначить и отложить выбор "на потом". Собственно, нам нужны эти группы для того, чтобы убедиться, что каждое значение действительно получит уникальный адрес, а если у нас уже в группе осталось одно, то мы это уже знаем. Возможно, занесём его теперь в ОБЕ группы.
Собственно, не будем приводить здесь все 64 группы, это слишком жестоко... Интрига сохранилась только в группе 0 (там два значения, которых должен РАЗДЕЛИТЬ следующий бит). Была 15-я группа с 2 числами:
30 = 0x001E = xxxx_xxxx_0001_1110 21758 = 0x54FE = 0101_0100_1111_1110
Но по 8-му биту она тоже замечательно разделилась на 2, под номерами 60 и 61 (собственно, группа с номером N делится на группы с номерами 2N и 2N+1).
Так что всё идёт неплохо.
Рассматриваем 9-й бит с конца
А вот тут у нас количество "x" начинает просто зашкаливать! Из всех 25 значений, только 6 имеют ширину 16 бит. Это математические константы, которые используются в АЛУ: внезапно НОЛЬ (поглядим, нельзя ли Acc 0 заменить на ZAcc RoundZero, но алгоритм составления QuatCoreImm должен работать при ЛЮБЫХ наших причудах!), ЕДИНИЦА (использовалась в DIV2S 1, чтобы из значения в аккумуляторе вычесть 1/2 младшего разряда), и ещё веса для Манхэттенской и Чебышевской метрик (чтобы из них получить худо-бедно Эвклидову), число 1/2, тоже какбе вещь полезная. И впридачу нулевое приближение для метода Ньютона. Все остальные значения: 8-битные или даже 5-битные.
Итак, получаем офигительную сигнатуру:
xx0x_0xxx_xxxx_x1xx_0xxx_xxx0_0
И, как это ни странно - СОВПАДЕНИЙ ВСЁ РАВНО НЕ НАЙДЕНО!
Это вот уже обидно: нужно-то было лишь совпадение в 6 местах, и было 8 строк, хоть одна должна была совпасть - но нет.
И сопоставить этот бит с SrcAddr[6] мы тоже не можем, так как значения 0 и 16384 "не разделяются" этим битом.
Так что этот бит должен выражаться через логическую функцию от других адресов, и откладываем его на потом...
Рассматриваем бит 10 с конца
Его сигнатура отличается от предыдущего всего одним значением (в самом конце) и равна:
xx0x_0xxx_xxxx_x1xx_0xxx_xxx1_0
И снова неудача... И сопоставить этот бит с SrcAddr[6] нельзя, значения 0 и 16384 "не разделяются".
Тоже должны выразить через логическую функцию - но позже...
Рассматриваем бит 11 с конца
И он не шибко отличается от предыдущих:
xx0x_0xxx_xxxx_x0xx_0xxx_xxx0_1
Но в кои-то веки совпадения появились, одновременно с 3-м, 4-м и 5-м битом! А раз так, мы можем записать:
assign Q[10] = SrcAddr[2];
и дело с концом.
Рассматриваем 12-й бит с конца
Оказывается, он полностью совпадает с битом 10, и хотя для 10-го бита мы пока не записали логическую функцию, можем сразу с ним соединить и 12-й:
assign Q[11] = Q[9];
Отсюда вывод: сигнатуры мы заносим даже для тех битов, которые мы "отложили на потом", хотя насчёт "don't care" ещё предстоит немного подумать.
Рассматриваем 13-й бит с конца
Он полностью совпадает с битом 11, так что и здесь сразу вписываем:
assign Q[12] = Q[10];
Подобную вещь я вполне ожидал, когда отдельные старшие биты не будут шибко уникальными. Тут "закон больших чисел" играет в мою сторону - одно дело найти две строго одинаковые 25-битные последовательности, а другое дело - две 6-битные.
Рассматриваем 14-й бит с конца
Он совпадает с 12-м и 10-м:
assign Q[13] = Q[9];
И я так понимаю, если у нас есть повторение, оно заведомо не может "разделить" значения внутри наших групп, поскольку один раз такое разделение уже было сделано.
Рассматриваем 15-й бит с конца
Вот он уж точно ни с каким не совпадёт, поскольку только в нём одна-единственная "единичка" в числе 16384 = 0x4000.
Вот его-то мы и соединяем с последним доступным битом адреса SrcAddr[6]:
assign Q[14] = SrcAddr[6];
Рассматриваем 16-й бит с конца, он же самый первый :)
Ни с какими другими он не совпадает, и биты адреса у нас уже закончились, значит, и он должен выражаться через логическую функцию.
Предварительный итог
Вот биты, которые мы уже выразили:
assign Q[0] = SrcAddr[0]; assign Q[1] = SrcAddr[1]; assign Q[2] = SrcAddr[2]; assign Q[3] = SrcAddr[3]; assign Q[4] = SrcAddr[4]; assign Q[7] = SrcAddr[5]; assign Q[10] = SrcAddr[2]; assign Q[11] = Q[9]; assign Q[12] = Q[10]; assign Q[13] = Q[9]; assign Q[14] = SrcAddr[6];
И мало того: в номере группы, где содержится конкретное значение, закодирован адрес SrcAddr[] для данного значения. Поэтому все остальные биты, Q[5], Q[6], Q[8], Q[9] и Q[15], можно выразить через логические функции от SrcAddr[]. Здесь тоже есть подход "в лоб": честно записать в верилоговском коде все 128 различных адресов, и для каких-то из них указать don't care, а где надо - единицы и нолики. Но это очень уродливо. Лучше было бы тоже поискать как бы здесь устроить функцию всего от 2 входов, а если такой нет - от трёх, и в самом крайнем случае от четырёх.
Продолжение следует...
