Форум DL

Мой профиль

Давайте собирать в этой теме интересные к разработке цифровые устройства, например:

- N*N Input Queued fixed size packet switch

  each input has N FIFO queue - one for each output
  In each time slot ar most one packet arrives at each
  input and at most one packet can transfer to an output
  Switch sheduling algorithm:

  MWM   - maximum-weight matching - O(n^3)
  iSLIP - iterative SLIP
  iLQF  - iterative longest queue first
  PRA   - reservation with preemption and acknowledgement
  MUCS  - matrix unit cell sheduler

- Ternary Content Addressable Memory (TCAM)

  store don't care states in addition to 0's and 1's.
  TCAMs search data (IP address) in a single clock cycle.

  SW approach take at least 4-6 memory accesses for a
  single look-up operation.

  Binary CAM request 1 memory access,  but allow only
  fixed length comparisons. So they unsuitable for longest
  prefix problem.

  TCAM solves the longest prefix problem.

  Today routing tables (March 2004) have ~125,000 entries
  and will contain 250,000 entries by 2005.

  Paged TCAM reduces power consumption
    - Prefixes are partioned into 8 groups of equal size.
      Each group resides on a separate TCAM chip.

  LCS - largets common subprefix.

Мой профиль

Я пытался найти с помощью Inet устройства, которые задаются к проектированию в других вузах, вот только что мне удалось найти :-(

Релизовать конечный автомат в виде схемы управления:
1. двух лифтов.
2. автомата с газировкой.
3. светофоров на перекрестке.
4. светофоров (без перекрестка).
5. механизма подачи бумаги в принтере.
6. электронного кодового замка.
7. турникета в метро.
8. телефонного аппарата.
9. банкомата по выдаче денег.
10. калькулятора.

Мой профиль

А это список разновидностей процессоров
(можно пытаться проектировать их фрагменты)

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

Мой профиль

Вот задачи на разработку программ/устройств с побитовой обработкой

Дано двух байтовое число
- вывести только четные (нечетные) его 16-ричные цифры
- вывести его 16-ричные цифры, стоящие на четных/нечетных позициях
- вывести его двоичные цифры, стоящие на четных/нечетных позициях

Можно все те же задачи для 4-байтового числа

Можно все те же задачи для числа, длина которого в байтах ЗАДАЕТСЯ в специальной байтовой переменной L.

Вот именно такого сорта (и в этом направлении, но еще сложнее или более приближенные к реальным) задачи и хотелось бы видеть установленными на DL в качестве "новых задач" для учебных курсов, связанных с изучением аппаратного и низкоуровневого программного обеспечения вычислительных средств.

Мой профиль

Вот еще задачи на побитовую обработку, навеяны вопросам Саши Рожкова, за что ему огромное спасибо (и +1 бонусный балл).

Все задачи можно/нужно решать программно и/или аппаратно:

1. Реализовать битовый вектор длины 1024 с операциями чтения записи бита по указанному адресу.

2. Реализовать битовый вектор длины 1024 с операциями чтения записи группы битов фиксированной длины по указанному адресу.

3. Реализовать битовый вектор длины 1024 с операциями чтения записи группы битов задаваемой длины по указанному адресу.

4. Реализовать двумерный битовый массив фиксированной размерности
(например, 256*16) с операциями
- чтения/записи слова по указанному адресу
- чтения/записи бита по указанному адресу

5. Реализовать двумерный битовый массив переменной размерности
с операциями
- чтения/записи слова по указанному адресу
- чтения/записи бита по указанному адресу

6. Реализовать трехмерный битовый массив фиксированной размерности с операциями
- чтения/записи плоскости по указанному адресу
- чтения/записи слова по указанному адресу
- чтения/записи бита по указанному адресу

7. Реализовать трехмерный битовый массив переменной размерности
(например, 8*8*8) с операциями
- чтения/записи плоскости по указанному адресу
- чтения/записи слова по указанному адресу
- чтения/записи бита по указанному адресу

Мой профиль

А вот еще серия задач на работу с битами.
Супер-лаконичные и элегантные решения этих задач находятся в книге
"Алгоритмические трюки для программистов"
Генри Уоррен, мл., Москва, "Вильямс", 2004, 288 с.
Сами условия задач взяты там же.

c.25-26

 1. Обнулить крайний справа единичный бит. 
    Например,  01011000 => 01010000.
 2. Проверить, является ли беззнаковое целое число степенью двойки.
 3. Выделить в слове крайний справа единичный бит.
    Например,  01011000 => 00001000.
 4. Выделить в слове крайний справа нулевой бит.
    Например,  10100111 => 00001000.
 5. Создать маску, идентифицирующую завершающие нулевые биты.
    Например,  01011000 => 00000111. 
    Если число равно 0, то результат - все 1: 00000000 => 11111111.
 6. Создать маску, идентифицирующую крайний справа единичный бит 
    и завершающие нулевые биты.
    Например,  01011000 => 00001111. 
    Если число равно 0, то результат - все 1: 00000000 => 11111111.
 7. Распространить вправо крайний правый единичный бит.
    Например,  01011000 => 01011111.
    Если число равно 0, то результат - все 1: 00000000 => 11111111.
 8. Обнулить крайнюю справа непрерывную подстроку единичных битов.
    Например,  01011000 => 01000000.
 9. Проверить, имеет ли положительное целое число вид 2^j-2^k

ТЕОРЕМА:
Функция, отображающая слова в слова, может быть реализована посредством операций побитового сложения, вычитания, и, или, отрицания, тогда и только тогда, когда каждый бит результата зависит только от битов исходных операндов в той же позиции и правее (младше) нее.
с.27-28

10. Обнулить крайний слева единичный бит
11. Сдвиг вправо на переменную величину
12. Циклический сдвиг на переменную величину
13. Сдвиг влево на переменную величину
14. Количество завершающих нулевых битов в слове
15. Сортировка битов
16. Найти следующее число, которое больше заданного, но имеет такое
    же количество единичных битов
17. Количество ведущих нулевых битов в слове
18. Количество единичных битов

с.31-34



19. Абсолютное значение

20. Распространение знака

21. Функция sign

22. Трехзначная функция сравнения

23. Перенос знака

с.46

24. Циклический сдвиг влево на n разрядов
25. Циклический сдвиг вправо на n разрядов

с.48



26. Сдвиг двойного слова влево на n разрядов

27. Безнаковый сдвиг двойного слова вправо на n разрядов

28. Знаковый сдвиг двойного слова вправо

с.50-52

29. Функция doz(x,y)=x-y, если x>=y и 0 в противном случае
30. Функция Max(x,y)
31. Функция Min(x,y)
32. Обменять биты двух регистров x и y, если i-тый бит маски (m[i])
    равен 1, и оставить их неизменными, если m[i]=0
33. Обмен двух полей (одинаковой длины) одного регистра.
34. Условный обмен битов двух регистров
35. Условный обмен полей одного регистра

c. 57-60



36. Округление к кратному степени 2

37. Округление к ближайшей степени 2

38. Количество ведущих нулевых битов

39. Округление в меньшую сторону

40. Округление в большую сторону

с.64-65

41. Проверка границ целых чисел
42. Определение границ суммы и разности

с.70-72



43. Вычисление нижней  границы x | y

44. Вычисление верхней границы x | y

45. Вычисление нижней  границы x & y

46. Вычисление верхней границы x & y

с.75-87

47. Подсчет количества единичных битов в слове
48. Подсчет единичных битов в малозаполненных словах
49. Подсчет единичных битов в массиве
50. Расстояние Хемминга
51. Проверка на четность
52. Добавление бита четности к 7-битовой величине
53. Подсчет ведущих нулевых битов

с.92-97



54. Подсчет завершающих нулевых битов

55. Алгоритм Госпера, обнаруживающий циклы

56. Алгоритм Флойда, обнаруживающий циклы

с.104

57. Поиск строки единичных битов заданной длины

с.107-121



58. Реверс битов в слове

59. Обобщенный реверс битов

60. Реверс байтов в слове

61. Реверс битов в каждом байте

62. Увеличение обращенного целого

63. Идеальное внешнее перемешивание битов

64. Идеальное внутреннее перемешивание битов

65. Транспонирование битовой матрицы 8*8

66. Транспонирование битовой матрицы 32*32

67. Сжатие, или обобщенное извлечение

с.126

68. Обобщенное упорядочивание (SAG)

с.227-230



69. Четырехбитовый код Грея по бинарному

70. Четырехбитовый бинарный код по коду Грея

71. Генерация кода Грея 

72. Увеличение чисел кода Грея

с.235-247

73. Генерация кривой Гильберта
74. Преобразование расстояния вдоль кривой Гильберта в координаты
75. Преобразование координаты в расстояние вдоль кривой Гильберта
76. Увеличение координат кривой Гильберта
77. Добавление одного звена кривой Гильберта

Мой профиль

Игорь Викторович Коршунов реализовал в HLCCAD-е возможность указывать в задании разрешенные или запрещенные устройства. Подробно как это делать описано
здесь:

В результате появилась возможность (и давно существует огромная потреность) в разработке заданий на ДВЕ ТЕМЫ:
1. Проектирование стандартных устройств на логических элементах
2. Каскадирование стандартных устройств

Перечень стандартных устройств с их обозначениями:

Логические элементы
AND OR XOR NOT

Комбинационные схемы
DC - дешифратор
CD - шифратор
MS - мультиплексор
DMS - демультиплексор
SUM - сумматор

Устройства памяти
T - триггер
RG - регистр
CT - счетчик
RAM - ОЗУ - оперативное запоминающее устройства
ROM - ПЗУ - постоянное запоимнающее устройство

Арифметические схемы
CMP - схемы сравнения
MUL - умножитель
DIV - делитель

Вот примеры заданий ОБОИХ ВИДОВ:

1. Разработать стандартные устройства (можно использовать только И-ИЛИ-НЕ любой разрядности)
DC(2-4/3-8/4-16)
CD(4-2/8-3/16-4)
MS (2-1/4-1/8-1/16-1)
SUM(1/2/4/8),
T, RG(1/2/4), CT(1/2/4),
RAM (4*2)/ROM(4*2)

2. Задание на каскадирование
DC (4-16) из DC (2-4), DC (5-32) из DC (3-8),
аналогично для всех стандартных устройств

Мой профиль

Примеры заданий по лекциям:
Можно делать HLLCAD-проекты либо C-MPA программы

Особенности архитектуры 8086

1. Распространение знака CBW, CWD
2. Выборка байтного/словного регистра по mod/rm
3. Управление флагами (CLC ... CMC)
4. Работа со стеком
5. INC, DEC
6. XCHG
7. Условный переход Jxxx
8. Вызов подпрограммы CALL
9. Прерывание INT
10. Логический сдвиг
11. Арифметический сдвиг
12. Кольцевой сдвиг
13. Кольцевой сдвиг через бит CF
14. Целочисленное умножение
15. Целочисленное деление

Особенности архитектуры 80286

1. Вычисление физического адреса в реальном режиме
2. Вычисление физического адреса в виртуальном режиме
3. Общая схема адресации в виртуальном режиме (Лекция 4/9)
4. Вычисление физического адреса в защищенном режиме (Лекция 4/12)
5. Контроль привилегий (Лекция 4/19)

Особенности архитектуры 80386

1. Реализация индексного режима адресации с масштабированием
2. Быстрое завершение умножения
3. Операции над битами (BT,BTC,BTS,BTR)
4. Операции над битами (BSF,BSR)
5. Операции над байтами/словами MOVZX, MOVSX
6. Двойные сдвиги (SHLD, SHRD)
7. Вычисление физического адреса в защищенном режиме (Лекция 5/16)
8. Механизм страничной организации ОП (Лекция 5/18)
9. Буфер ассоциативной трансляции
10. Кеш-память (Лекция 5/22)

Особенности архитектуры 80486

1. Обменять байты BSWAB
2. Обменять и сложить XADD
3. Cравнить и обменять CMPXCHG
4. Кеш-память i486 (Экран "Лекция 6/8")
5. Реализация алгоритма LRU (Экран "Лекция 6/9")
6. Буфер ассоциативной трансляции (Экран "Лекция 6/10")
7. Блок отладочных регистров (Экран "Лекция 6/19")

Особенности архитектуры Pentium

1. Кеш для динамического прогнозирования ветвлений
2. Схемы контроля четности
3. Сложение вещественных чисел
4. Вычитание
5. Умножение
6. Деление

Команды MMX

1. Упакованное сложение слов с насыщением (PADDSW)
2. Упакованное умножение слов со сложением (PMADDWD)
3. Параллельное сравнение PCMPEQ [B, W, D] (на равно)
4. Параллельное сравнение PCMPGT [B, W, D] (на больше)
5. Логический сдвиг на переменное число разрядов PSLL [B, W, D]
6. Арифметический сдвиг на переменное число разрядов PSLL [B, W, D]

Мой профиль

Задания на разработку устройств с использованием шифратора, предложенные студентами группы ПО-31 (2009)

Мой профиль

Задания на битовую обработку, предложенные студентами группы ПМ-41 и ПМ-42

Ушанов Николай
Дана 16-битная последовательность. Составить последовательность состоящую из четных битов исходной последовательности.

Харлан Надежда
Даны две последовательности X и Y по 8 бит. Результат равен количеству битов на одинаковых позициях в X и Y, не совпадающих по значению.

Боневич Екатерина
Даны две 8-битных последовательности X и Y. Если на i-том месте в последовательности X стоит 1, а на этом же месте последовательности Y стоит 0, то увеличить выходную переменную на номер i.

Шруб Борис
На входе 16-битная последовательность. Удалить нули, стоящие на четных позициях (0,2,4,...)

Чванькова Татьяна
Нумерация битов справа налево и начинается с 1.
Найти первые 2 бита = 01 и последние 2 бита = 11 и поменять их местами.

Мой профиль

Задачи на использование мультиплексора, предложенные студентами группы ПО-31:

Баразновский Владимир
- максимальное из 5 чисел
- удалить n-ый бит
- сортировка 5 чисел
- на входе 8-битовая последовательность и n. Если n<=4 то зеркалировать старшие биты, иначе младшие

Шведов Андрей
- на вход подается 8 битов данных и два входа по 3 бита. Необходимо в исходной последовательности поменять местами биты с указанными номерами

Войтович Павел
- Даны 8-битовая последовательности Z и X. Вывести те биты последовательности Z, которые стоят на позициях, в которых биты X равны 0. Все старшие биты в Z заполнить нулями.

Короленок Павел
Дана последовательность из 8 бит и 3-битное число n. Инвертировать n первых бит 8-битной последовательности.

Дана последовательность из 8 бит и 3-битное число n. Заменить нулем n первых бит 8-битной последовательности.

Кудра Игорь
Дана последовательность из 256 бит. Найти максимальное число, которое может быть получено тройками из этого числа.

Поляков Андрей
На входе дана некоторая 8-битная последовательность, рассматриваемая как число. Если число кратно 2, то подать на выход второй бит, если кратно трем, то 3-ий бит, если четырем, то 4-ый бит. и т.д. При одновременной кратности приоритетным является больший делитель. То есть если число кратно 5 и 2, на выход подается 5-ый бит. Если на входе простое число (кроме 3 5 и 7), подать на выход 1-ый бит.

На входе последовательность из 8 бит. Сложить все биты. Если сумма равно 0 по давть на выход четные биты (0-ой, 2-ой, 4-ый и 6-ой) иначе - нечетные (1 3 5 7).

Климович Дмитрий
"Детский сад"
Воспитатель указывает цифры А и В (обе по 4 бита)и знак между ними 1 бит (+ 1, - 0). Ребенок на панельке нажимает ответ (одна из 10 линий 0 - 9). Устройство выходом (1) включает лампочку при правильном ответе.

Ильющенко Сергей
Два входа - 8 битный и 3-битный, поменять местами бит указанный 3-битным номером и старший бит.

Белякова Ангелина
Два входа - 8 битный и 3-битный. До номера - заменить на 0, остальные инвертировать.

На входе 8 битная последовательность. Вывести бит этой последовательности, номер которого задается тремя ее старшими битами.

Чаховский Дима
Вывести бит из последовательности, номером которого является сумма битов входной последовательности.

Вывести старшую или младшую половину исходной последовательности, в зависимости от того, где больше единичных битов.

Тюленкова Ольга
Дана 8-битная последовательность. Если в ней содержится четное число единиц, вывести ее, иначе - инвертированную.

Мой профиль

Задачи по курсу "Архитектура вычсилительных систем", предложенные командами из группы ПО-21

Вераксич Сергей, Зайцев Олег, Ратников Алексей

1.1. BSF (80386)
На входе 16 бит, число X. Найти номер самой младшей единицы и вывести ее номер в Y (4 бита).
Пример: X=1101100110101100
Y=2
1.2. (?)BSWAB (80486)
На входе 16-битное число X. Поменять в нем порядок следования битов на обратный и занести
результат в Y (16 бит).
Пример: X=1011011100111010
Y=0101110011101101
1.3. CWDE
Дано 16-битное число. Расширить его до 32-битного, учитывая знак. X – вход, Y – выход.
Пример: X=1111010011011110
Y=11111111111111111111010011011110
1.4. CMPXCHG (80486)
Даны 2 числа. X и Y по 16 бит. Нужно записать X в Y, Y в X, а также 0,1 или 2 в C
(0, если X=Y, 1 если X>Y, 2, если X<Y)
Пример: Х=5, Y=6 => X=6, Y=5, C=2

Громыко Александр, Калачева Екатерина, Федоренко Антон

2.1. ? Реализовать команду коррекции деления AAD.
Входные данные данные (X) 16 бит, выходные (Y) – 16 бит.
2.2. ? Реализовать команду коррекции умножения AAM.
Входные данные данные (X) 16 бит, выходные (Y) – 16 бит.
2.3. Реализовать команды SHLD и SHRD
Входы: X – 1 бит, O1 – 8 бит, O2 – 8 бит.
? Выход OUT – 8 бит
Если x=0, То реализовать SHLD, иначе – SHRD.
2.4. Реализовать команду BT
На вход подается 2 значения OP1 и OP2 по 16 бит.
На выход CF подать значение бита числа OP1 с номером OP2.
Нумерация бит начинается с 0.
2.5. Реализовать команду арифметического сдвига влево/вправо.
?На вход подается число a (16 бит) и символ SA. Если в SA
содержится “L”, то сдвиг влево, на CL (16 бит) бит. Иначе
если SA=”R”, то сдвиг вправо. Выход a1 (16 бит)
Все остальные команды – задачи НЕ НА ТЕМУ ЛЕКЦИЙ

Мой профиль

Задачи на тему "Устройства с памятью" от студентов группы ПО-31:

Журавлев
Разработать устройство для шахмат, определяющее победителя и проигравшего по истечении времени.
На вход D подается начальное значение времени.
C - вход тактовых импульсов
M1 - кнопку нажал первый игрок (время запускается у второго)
M2 - кнопка второго игрока

P1 - время вышло у первого игрока
P2 - -"- у второго

Климович
Задача "Соревнования"
Есть две кнопки. При нажатии на каждую добавляется единица в соответствующий счетчик. Побеждает тот, у кого больше нажатий.
Кнопка нажата - in1(2)=1, иначе in1(2)=0. R - сброс, Res - номер
победителя, ничья - Res=0.

Чаховский
Подсчитать, сколько раз пропадал сигнал (переход с 1 на 0) на входной линии line.

Мой профиль

Олимпиада по программированию микроконтроллеров апрель 2009

Имеется описания заданий, которые было бы интересно установить и на DL.

Мой профиль

Задания на тему "Компараторы" от студентов группы ПО-31(15 февраля 2010 года):

- Организовать сложение двух двухбитных чисел по модулю (Коноплев)
- Даны три 4-битовых беззнаковых числа. Подать на выход y1 максимальное, на выход y3 - минимальное, на y2 - оставшееся из чисел (Литвинов)
- Дано три числа (A,B,C - 4-битные, знаковые). На выход подать числа X,Y (4-битные, знаковые). X - максимальное из двух чисел, Y - второе по максимальности (Моисеенко).
- Даны A, B (4-битные) и C,D (8-битные). Выход r - 8 бит.
Если a*b>c то r=a*b+c иначе r=c+d (Федоренко)
- Спроектировать компаратор, который сравнивает двухбитное число с 4-битным (Ловкевич, Ратников)