nabbla (nabbla1) wrote,
nabbla
nabbla1

Categories:

QuatCore: реализуем таблицу непосредственных значений

Для начала: "вручную", чтобы получить какое-то представление, что нас ждёт, где имеет смысл "копать", а где шансов почти что нет.

Выпишем 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 входов, а если такой нет - от трёх, и в самом крайнем случае от четырёх.


Продолжение следует...
Tags: ПЛИС, программки, работа, странные девайсы
Subscribe

Recent Posts from This Journal

  • Нахождение двух самых отдалённых точек

    Пока компьютер долго и упорно мучал симуляцию, я пытался написать на ассемблере алгоритм захвата на ближней дистанции. А сейчас на этом коде можно…

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 2 comments