Форум DL

My Profile

10. Преобразователи кодов на ПЗУ
Базовая теория

Преобразователь BCD -> binary

Выставлены пропуски за неотработанный СУРС

Это намеренно сделано задолго до конца семестра.
Чтобы было достаточно времени сделать СУРС качественно, без спешки и нервотрепки. Или вообще его не делать, если оценка и так Вас устраивает.

Варианты отработки СУРСа

My Profile

Бонусы за работу на лекции 5 апреля
Федоренко - 10 (139->149)
Зубов - 5 (32->37)

My Profile

Бонусы за указание на ошибку
Зайцев = 5 (71->76)
Полховский = 5 (10->15)

My Profile

10. Преобразователи кодов на ПЗУ
Базовая теория

Преобразователь binary -> BCD

My Profile

Бонусы за работу на лекции

Простой рисунок и ВЕСА на корпусах пирамиды,
подсказывающие решение (!!!):
60: Коноплев (79->139)

Системно нарисованные схемы:
40: Макаревич(27->67), Ратников(83->123), Калачева(87->127),
Моисеенко(79->119), Вераксич(96->136), Громыко(99->139), Федоренко(149->189)

Неаккуратно/несистемно нарисованные схемы
20: Гладченко(66->86), Литвинов(72->92), Цвиликов(29->49), Зайцев(76->96)

У остальных схемы или не дорисованы, или явно не правильны.

---------------------------------------------------------------

Веса на младших линиях на схеме Коноплева
по рядам слева-снизу вправо-вверх
1 ряд: 512, 128, 32, 8, 2
2 ряд: 640, 160, 40, 10,
3 ряд: 800, 200

Очевидны закономерности (открытые Коноплевым):
- деление на 4, числа подаваемого на младшую входную линию
- ряд пирамиды завершается, когда на младшей выходной линии появляется число из выходного ряда
(1,2,4,8, 10,20,40,80, 100,200,400,800, 1000,2000,4000,8000)

Хорошо бы еще понять какова закономерность в ПЕРВЫХ числах.
(512, 640, 800, ???)

Слава Коноплев:

по моему и для первых цифр закономерность очевидна.
Это сумма первого и второго числа предыдущего ряда.
640=512+128
800=640+160
...

Зачем нам это нужно?
Чтобы генерировать схемы автоматически.
Кстати - хорошие задания для СУРС.
- параметрические (количество линий на входе/максимальное число на входе) высокоуровневые модели конверторов (BCD->Binary, Binary->BCD)
- генераторы пирамидальных схем конверторов (BCD->Binary, Binary->BCD)

My Profile

Цифровые устройства сортировки:
Каскадирование и микропрограммирование.
1. Сортировщик 2 чисел
2. Сортировщик 4 чисел
3. Схема каскадной сортировки N чисел
4. Сортировка потока байтов.
5. Реальные задачи на сортировку.

My Profile

по моему и для первых цифр закономерность очевидна.
Это сумма первого и второго числа предыдущего ряда.
640=512+128
800=640+160
...

My Profile

Коноплев : +10 (139->149) бонусов за закономерность, которую я сразу и не увидел.

Гладченко : +100 (86->186) бонусов за очень интересный вопрос
(быстрый алгоритм вычисления корня n-ой степени из целого числа)
и попытку его решения

My Profile

Сегодня было занятие по командной разработке устройств сортировки.
Все 24 присутствующих работали весьма активно.
Любо-дорого смотреть.

Все получают по 40 бонусов.

Реальные результаты работы будут бонусироваться отдельно после проверки сданных проектов.

My Profile

Обещанные 40 бонусов

Вераксич (136->176) Гатальский (24->64)  Гладченко (186->226)  Громыко   (139->179)
Зайцев    (96->136) Зубов      (37->77)  Иванчук     (7->47)   Калачева  (127->167)
Коноплев (149->189) Кравцова   (25->65)  Леоненко     (1->41)  Литвинов   (92->132)
Ловкевич  (19->59)  Макаревич  (67->107) Моисеенко  (119->159) Мороз       (1->41)
Пискунова (16->56)  Ратников  (123->163) Тараренко    (4->44)  Федоренко (189->229)
Ходанович (18->58)  Цакунов    (13->53)  Цвиликов    (49->89)  Юдченко    (33->73)

My Profile

Гладченко, Коноплев, Цвиликов 60 бонусов/3= по 20
- аппаратная сортировка двух чисел
- наглядная и потому почти доказанная схема сортировки 4 чисел
на базе сортировщиков двух чисел

    s2      s2      
                     s2
    s2      s2

- наглядная и потому почти доказанная(?) АНАЛОГИЧНАЯ схема сортировки N чисел
на базе сортировщиков N/2 чисел

==n/4 ======    ======= n/4 ===     ====(n/4)==========================
            sN/2                sN/2 
==n/4 ======    \  ==== n/4 ===     ====(n/4)=====       ====(n/4)=====
                 \/                                sN/2
                 / \                                     ====(n/4)=====
==n/4 ======    /   \==== n/4 ===   ====(n/4)=====
            sN/2                sN/2
==n/4 ======    ========= n/4 ===   ====(n/4)==========================

- микропрограммная не по определению сортировка потока байтов

Вераксич, Зайцев, Макаревич, Ратников 56 бонусов /4= по 14
- аппаратный сортировщик двух чисел (вместо MS своя комбинационная схема)
- не совсем наглядная недоказанная аппаратная схема сортировки 4 чисел

       s2       s2
                        s2
       s2       s2

- наглядная недоказанная аппаратная схема сортировки N чисел
на базе сортировщика N/2 чисел

       sN/2   sN/2 
                           sN/2
       sN/2   sN/2

Примеры устройств, применяющих сортировку
- роутер хранит список IP-адресов, имеющих доступ во внешнюю сеть.
Реализовать устройство, которое решает по исходящему адресу пакета,
пропустить его или нет.
Идея решения: используем сортировщик для быстрой сортировки
хранимых адресов. Для решения пропускать пакет или нет, используем
двоичный поиск исходящего адреса в списке доступных адресов

Калачева, Федоренко, Громыко, Тараренко 52 бонуса/4= по 13
- стандартная сортировка 2-х чисел (cmp+2ms)
- наглядная (недоказанная) схема сортировки 4 чисел:

      s2          s2
             s2          s2
      s2          s2

- описание сортировки N чисел с пояснениями (без схемы)
- описание алгоритма сортировки потока байтов, ориентированного на программную реализацию
Примеры устройств, применяющих сортировку
- на вход подаются результаты 32 испытаний, нужно выбрать 5 лучших результатов
- на вход подается 16 значений, нужно посчитать среднее за исключением трех лучших и трех худших

Литвинов, Моисеенко 30 бонусов/2= по 15
- сложная (6 умножителей и два сумматора) и недоказанная сортировка двух чисел
- нечитабельная и недоказанная схема сортировки 4-х чисел
- еще версия сортировки двух чисел (три умножителя, один сумматор)
- неструктурированное и труднопонимаемое описание сортировки N чисел
на базе сортировщика N/2 чисел
- фрагмент микропрограммы сортировки потока байт
Примеры устройств, применяющих сортировку
- в электронной записной книжке данные хранятся в отсортированном порядке для ускорения поиска
- в медиа-плейерах субтитры отсортированы по времени

Ловкевич, Пискунова, Мороз, Иванчук, Зубов 25 бонусов/5= по 5
- аппаратный сортировщик двух чисел с параметром «направление сортировки»
- микропрограммный сортировщик двух чисел с параметром «направление сортировки»
- микропрограммный сортировщик 4 чисел с параметром «направление сортировки»
- наглядная (недоказанная) схема сортировки 4 чисел:

     s2       s2        s2
         s2        s2
              s2

- наглядная, недоказанная схема сортировки 8 чисел на базе сортировщиков 4 чисел:

    s4                                       s4 
          s4                             s4
                s4                  s4
                      s4       s4
                            s4

- непонятная и недоказанная идея сортировки N чисел
Примеры устройств, применяющих сортировку
- даны 8 чисел, отсортировать первые 4 числа по возрастанию, последние 4 числа – по убыванию
- дано шестизначное число, отсортировать цифры этого числа по убыванию
- про сортировку объединения двух строк (совсем не в тему)

Гатальский, Ходанович, Леоненко, Юдченко 20 бонусов/4 = по 5
- аппаратный сортировщик двух чисел (cmp+2ms)
- ненаглядная недоказанная схема сортировки 4 чисел

     s2      s2
                       s2
     s2      s2

- ненаглядная недоказанная схема сортировки 8 чисел:

     s4      s4
                   s4
     s4      s4          s4

- микропрограммная реализация сортировки N чисел

Кравцова 5 бонусов
- аппаратный сортировщик двух чисел
- аппаратный сортировщик трех чисел на базе мультиплексоров

20: Гладченко (226->246), Коноплев(189->209), Цвиликов(89->109)
14: Вераксич(176->190), Зайцев(136->150), Макаревич(107->121), Ратников(163->177)
13: Калачева(167->180), Федоренко(229->242), Громыко(179->192), Тараренко(44->57)
15: Литвинов(132->147), Моисеенко(159->172)
5: Ловкевич(59->64), Пискунова(56->61), Мороз(41->46), Иванчук(47->52), Зубов(77->82)
5: Гатальский(64->69), Ходанович(58->63), Леоненко(41->46), Юдченко(73->78)
5: Кравцова (65->70)

My Profile

15: Литвинов(132->147), Моисеенко(159->172)

172 - 159 = 13

My Profile

Виноват, исправился, 174

My Profile

Калачева, Федоренко, Громыко, Тараренко 52 бонуса/4= по 13
- стандартная сортировка 2-х чисел (cmp+2ms)
- наглядная (недоказанная) схема сортировки 4 чисел:

      s2          s2
             s2          s2
      s2          s2

Мы использовали стандартную сортировочную сеть для решения данной задачи. Ниже приведено доказательство которое можно найти в книге "Алгоритмы построение и анализ. Второе издание. / Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. - М.: Вильямс, 2005. - 1296с." + наши рассуждения для степеней двойки.

Доказательство:

Нуль-единичный принцип (zero-one principle) утверждает, что если сортировочная сеть правильно работает для всех наборов входных величин, составленных из элементов множества {0,1}, то она правильно работает для любых входных чисел. (Эти числа могут быть целыми, действительными или любым другим подмножеством величин, извлеченных из произвольного линейно упорядоченного множества.) При построении сортирующих сетей или других сравнивающих сетей нуль-единичный принцип позволяет ограничиться операциями, выполняющимися над последовательностью, составленной только из нулей и единиц. Построив сортирующую сеть и доказав, что с ее помощью сортируются все последовательности из нулей и единиц, можно обратиться к нуль-единичному принципу и доказать, что она надлежащим образом сортирует последовательности, составленные из произвольных величин.

Доказательство нуль-единичного принципа основано на понятии монотонно неубывающей функции (раздел 3.2).

Лемма 1. Если сравнивающая сеть преобразует входную последовательность a = <a1, a2, …, an> в выходную последовательность b =<b₁, b₂, …, b_n>, то для любой монотонно неубывающей функции f эта сеть преобразует входную последовательность f(а) = <f(a₁), f(а₂) , …, f(а_n)> в выходную последовательность f(b) = <f(b₁), f(b₂), ..., f(b_n)>.

Доказательство. Сначала докажем, что если функция f монотонно неубывает, то отдельное сравнивающее устройство с входными значениями f(x) и f(y) выдаст результат f(min(х, у)) и f(max(х, у)). Затем докажем лемму по индукции.
Чтобы доказать сформулированное выше утверждение, рассмотрим сравнивающее устройство, на вход которого подаются величины х я у. Верхнее выходное значение такого устройства равно min(х, у), а его нижнее выходное значение — max(х, у). Предположим, что теперь на вход сравнивающего устройства подаются значения f(х) и f(у) (рис. 1). На верхний выход сравнивающего устройства выдается значение min(f(х), f(у)), а на нижний выход — значение max(f(х), f(у)). Поскольку функция f монотонно неубывающая, из неравенства x <= у следует неравенство f(ж) <= f(у). Следовательно, выполняются тождества
min(f(x),f(y))=f(min(x,y)),
max(f(x),f(y))=f(max(x,y)).

Таким образом, если на вход сравнивающего устройства подать значения f(x) и f(у), то на его выходе получим значения min(f(x), f(у)) и max(f(x), f(у)). На этом доказательство утверждения завершается.

Методом индукции по шагам продвижения вглубь по каждому проводу в сравнивающей сети общего вида можно доказать более сильное утверждение, чем то, которое сформулировано в лемме. Оно заключается в том, что если какой-нибудь провод получает значение ai в результате подачи в сеть входной последовательности a, то при подаче входной последовательности f(a) он получает значение f(а_i). Поскольку в этом утверждении идет речь обо всех проводах, в том числе и о выходных, его доказательство станет доказательством леммы.

В качестве базиса индукции рассмотрим провод на глубине 0, т.е. входной провод a_i. Результат получается тривиальным образом: если на вход сети подается сигнал f(а), то по входному проводу передается сигнал f(a_i). В качестве шага индукции рассмотрим провод, расположенный на глубине d >= 1. Этот провод является выходным в сравнивающем устройстве, расположенном на глубине d, а входные провода этого устройства находятся на глубине, строго меньшей d. В соответствии с гипотезой индукции, если входные провода сравнивающего устройства передают сигналы ai и aj при подаче в сеть входной последовательности а, то при подаче входной последовательности f(а) они передают сигналы f(a_i) и f(a_j). Согласно доказанному ранее утверждению, выходные провода рассматриваемого сравнивающего устройства передают сигналы f(min(a_j, a_j)) и f(max(a_i, a_j)). Так как при подаче в сеть входной последовательности а они передают сигналы min(а_i, a_j) и max(a_i, a_j), то лемма доказана.

f(x) -------*------- min(f(x),f(y))=f(min(x,y))
                   |
f(x) -------*-------max(f(x),f(y))=f(max(x,y))
Рис. 1. Работа сравнивающего устройства, иллюстрирующая доказательство леммы 1; функция f — монотонно неубывающая

Если сравнивающая сеть является сортирующей, то лемма 1 позволяет доказать сформулированное ниже замечательное утверждение.

Теорема 1 (Нуль-единичный принцип). Если сравнивающая сеть с n входами правильно сортирует все 2ⁿ возможных последовательностей, состоящих из нулей и единиц, то она правильно сортирует все последовательности чисел произвольного вида.

Доказательство. Предположим, что это не так, и сеть сортирует все нуль-едимичные последовательности, но существует последовательность, состоящая из произвольных чисел, которую сеть не может правильно отсортировать. Другими с ловами, существует входная последовательность <a₁, а₂, ..., а_n>, которая содержит элементы a_i и a_j связанные соотношением a_i < a_j, но после прохождения сети значение a_j расположено в выходной последовательности перед значением а_i. Определим следующую монотонно неубывающую функцию f:

        /
       | 0 при x <=a_i,
f(x) =<
       | 1 при x > a_i.
        \

Поскольку в выходной последовательности сеть помещает значение a_j перед зачением а_i, если на вход подается последовательность <a₁, a₂, ..., а_n>, то из леммы 1 следует, что она разместит значение f(a_j) перед значением f(a_i) в выходной последовательности, если на вход сети подается последовательность <f(a₁), f(a₂), …, f(a_n)>. Но так как f(a_j) = 1 и f(a_i)= 0, мы приходим к противоречию, что сеть не в состоянии правильно отсортировать нуль-единичную последовательность <f(a₁), f(a₂), …, f(a_n)>
ч.т.д

My Profile

Наши рассуждения:
Из выше описанных теорем мы доказываем правильность сортировка четырех элементов.

1)
0    0    0    0    0
  s2        s2
0    0    0    0    0
       s2        s2
0    0    0    0    0
  s2        s2
0    0    0    0    0

2)
0    0    0    0    0
  s2        s2
0    0    0    0    0
       s2        s2
0    0    0    0    0
  s2        s2
1    1    1    1    1

3)
0    0    0    0    0
  s2        s2
0    0    0    0    0
       s2        s2
1    0    0    0    0
  s2        s2
0    1    1    1    1

4)
0    0    0    0    0
  s2        s2
0    0    0    0    0
       s2        s2
1    1    1    1    1
  s2        s2
1    1    1    1    1

5)
0    0    0    0    0
  s2        s2
1    1    0    0    0
       s2        s2
0    0    1    0    0
  s2        s2
0    0    0    1    1

6)
0    0    0    0    0
  s2        s2
1    1    0    0    0
       s2        s2
0    0    1    1    1
  s2        s2
1    1    1    1    1

7)
0    0    0    0    0
  s2        s2
1    1    0    0    0
       s2        s2
1    0    1    1    1
  s2        s2
0    1    1    1    1

8)
0    0    0    0    0
  s2        s2
1    1    1    1    1
       s2        s2
1    1    1    1    1
  s2        s2
1    1    1    1    1

9)
1    0    0    0    0
  s2        s2
0    1    0    0    0
       s2        s2
0    0    1    0    0
  s2        s2
0    0    0    1    1

10)
1    0    0    0    0
  s2        s2
0    1    0    0    0
       s2        s2
0    0    1    1    1
  s2        s2
1    1    1    1    1

11)
1    0    0    0    0
  s2        s2
0    1    0    0    0
       s2        s2
1    0    1    1    1
  s2        s2
0    1    1    1    1

12)
1    0    0    0    0
  s2        s2
0    1    1    1    1
       s2        s2
1    1    1    1    1
  s2        s2
1    1    1    1    1

13)
1    1    1    0    0
  s2        s2
1    1    0    1    0
       s2        s2
0    0    1    0    1
  s2        s2
0    0    0    1    1

14)
1    1    1    0    0
  s2        s2
1    1    0    1    1
       s2        s2
0    0    1    1    1
  s2        s2
1    1    1    1    1

15)
1    1    1    0    0
  s2        s2
1    1    0    1    1
       s2        s2
1    0    1    1    1
  s2        s2
0    1    1    1    1

16)
1    1    1    1    1
  s2        s2
1    1    1    1    1
       s2        s2
1    1    1    1    1
  s2        s2
1    1    1    1    1

Таким образом правильность сортировки для 4х элементов доказана. Для любых n не являющихся степенями двойки правильность нашей сортировки доказывается анологичным способом.

Для степеней двойки мы решили устроить каскадирование, т.е. на самом деле нам не важны центральные элементы они всегда будут у нас отсортированны, а важную роль играют только крайние элементы на котороых будет происходить обмен. Таким образом любая последовательность степени двойки(больше чем для второй степени) сокращается до схемы представленной для сортировки 4х элементов. Таким образом позволяя легко осуществлять каскадирование.