Эдвард В. Вейч
Эдвард Уэстбрук Вейтч | |
---|---|
Рожденный | |
Умер | 23 декабря 2013 г. | (89 лет)
Гражданство | Американский |
Альма-матер | Гарвардский университет |
Известный | оптимизация цифровых схем |
Научная карьера | |
Поля | Информатика |
Эдвард Уэстбрук Вейтч (4 ноября 1924 г. - 23 декабря 2013 г.) [1] ) был американским учёным-компьютерщиком . Он окончил Гарвардский университет в 1946 году по специальности «Физика» , а затем получил ученые степени Гарварда по физике и прикладной физике в 1948 и 1949 годах соответственно. В своей статье 1952 года «Графический метод для упрощения функций истинности» [2] Вейтч описал графическую процедуру оптимизации логических схем , которая называется диаграммой Вейча . Год спустя (в 1953 году) метод был усовершенствован в статье Мориса Карно . [3] в то, что стало известно как карта Карно ( K-карта ) или карта Карно-Вейча ( KV-карта ).
Более поздние размышления о дизайне диаграммы
[ редактировать ]Вейтч писал о разработке диаграммы Вейча и ее интерпретации:
- Проблема заключается в том, как изобразить булеву функцию от n переменных так, чтобы человеческий глаз мог легко увидеть, как упростить функцию.
- Функция четырех переменных имеет шестнадцать входных комбинаций, а на диаграмме есть шестнадцать различных квадратов, которые необходимо заполнить из таблицы истинности, определяющей функцию.
- Основное различие между версиями Вейча и Карно заключается в том, что диаграмма Вейча представляет данные в двоичной последовательности, используемой в таблице истинности, в то время как карта Карно меняет местами третью и четвертую строки, а также третий и четвертый столбцы.
- Общее сообщество цифровых компьютеров выбрало подход Карно. Вейтч принял это решение, хотя в начале 1952 года, еще до своего выступления, он почти перешел на этот подход, но отказался от него. Несколько лет спустя несколько учебников описали К-карту, некоторые из них назвали ее диаграммой Вейча.
Оригинальная диаграмма Вейча
[ редактировать ]Было известно, что функцию можно представить в виде точек на углах n-мерного куба. Два смежных угла, например два в правом верхнем углу, можно определить как верхние правые углы, а четыре угла в передней части куба можно определить как передние углы. Для четырех, пяти или шести переменных проблема усложняется.
Изображение многомерного куба на плоской диаграмме, позволяющей легко увидеть эти взаимосвязи:
- Для трех измерений Вейч нарисовал набор квадратов 2×2 для верхней части куба и второй набор для нижней части куба с небольшим пространством между двумя наборами квадратов. В наборе 2×2 вверху группы упрощения представляют собой любую горизонтальную или вертикальную пару или все четыре ячейки. Единственные смежности между верхним и нижним наборами — это взаимно однозначное соединение между каждым квадратом верхнего набора и соответствующей ячейкой нижнего набора. Аналогичное правило применяется к случаям с четырьмя переменными, которые иногда изображаются как куб внутри другого куба со всеми соединенными соответствующими углами.
- Тогда диаграмма Вейча с четырьмя переменными будет представлять собой четыре набора 2 × 2 в большом квадрате с небольшим пространством между каждой парой наборов. Таким образом, горизонтальная пара в верхнем левом наборе может объединяться с совпадающей парой в нижнем левом наборе или с верхним правым набором или, возможно, со всеми четырьмя наборами, образуя группу из восьми ячеек.
- Для пяти переменных или шести переменных применяется то же правило. Диаграмма пяти переменных состоит из двух диаграмм четырех переменных, нарисованных рядом друг с другом с большим пространством между ними. Совпадения между двумя диаграммами с четырьмя переменными происходят между ячейками, расположенными рядом друг с другом, когда одна карта накладывается на другую.
В последнюю минуту перед презентацией Вейтч удалил расстояние между группами ячеек 2×2. Это было неудачное решение, поскольку из-за него пользователю было сложнее понять общую структуру функции, а также правила, которые Вейтч использовал при распознавании упрощений. В последние годы жизни перед своей смертью в 2013 году [1] Решая головоломки судоку, Вейтч узнал , что пробелы или жирные линии между группами квадратов могут быть очень полезны, особенно если у человека плохое зрение, как у Вейча.
Ссылки
[ редактировать ]- ^ Перейти обратно: а б «Эдвард Уэстбрук Вейтч» (Некролог). Новости основных СМИ. 06 января 2014 г. Архивировано из оригинала 22 декабря 2015 г. Проверено 22 января 2015 г.
- ^ Вейч, Эдвард Уэстбрук (3 мая 1952 г.) [02 мая 1952 г.]. «Диаграммный метод для упрощения функций истинности». Протоколы ежегодного собрания ACM 1952 года . Ежегодная конференция/Ежегодное собрание ACM: материалы ежегодного собрания ACM 1952 года (Питтсбург, Пенсильвания, США). Нью-Йорк, США: Ассоциация вычислительной техники (ACM): 127–133. дои : 10.1145/609784.609801 . S2CID 17284651 .
- ^ Карно, Морис (ноябрь 1953 г.) [23 апреля 1953 г., 17 марта 1953 г.]. «Метод карт для синтеза комбинационных логических схем» (PDF) . Труды Американского института инженеров-электриков, Часть I: Связь и электроника . 72 (5): 593–599. дои : 10.1109/TCE.1953.6371932 . S2CID 51636736 . Документ 53-217. Архивировано из оригинала (PDF) 16 апреля 2017 г. Проверено 16 апреля 2017 г.
Дальнейшее чтение
[ редактировать ]- Комитет AIEE по техническим операциям для презентации на летнем общем собрании AIEE, Атлантик-Сити, Нью-Джерси, 15–19 июня 1953 г.
- «Натали Форд Вейч, Паоли, Пенсильвания» . Legacy.com (Некролог). 13 мая 2005 г. Архивировано из оригинала 7 августа 2019 г. Проверено 7 августа 2019 г.
- Вейч, Эндрю Ф. (01 октября 2012 г.) [ок. 2010-е]. «Личная переписка и комментарии Эдварда Уэстбрука Вейча в последние годы его жизни» . Архивировано из оригинала 7 августа 2019 г. Проверено 7 августа 2019 г. (Примечание. Это самостоятельно опубликованный первоисточник, но его стоит упомянуть здесь по историческим причинам.)