Эдвард В. Вейтч

Американский учёный-компьютерщик

Эдвард Уэстбрук Вейтч (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] Вейтч узнал, решая головоломки судоку , что пробелы или толстые линии между группами ячеек могут быть очень полезны, особенно если у человека плохое зрение, как у Вейтча.

Ссылки

1. "Эдвард Уэстбрук Вейтч" (некролог). Main Line Media News. 2014-01-06. Архивировано из оригинала 2015-12-22 . Получено 2015-01-22 .
2. Veitch, Edward Westbrook (1952-05-03) [1952-05-02]. "Метод диаграмм для упрощения функций истинности". Труды национального собрания ACM 1952 года (Питтсбург) на - ACM '52 . Нью-Йорк, США: Ассоциация вычислительной техники . стр. 127–133. doi :10.1145/609784.609801. S2CID  17284651.
3. Карно, Морис (ноябрь 1953 г.) [1953-04-23, 1953-03-17]. "Метод карты для синтеза комбинационных логических схем" (PDF) . Труды Американского института инженеров-электриков, часть I: Связь и электроника . 72 (5): 593–599. doi :10.1109/TCE.1953.6371932. S2CID  51636736. Статья 53-217. Архивировано из оригинала (PDF) 2017-04-16 . Получено 2017-04-16 .

Дальнейшее чтение

• Комитет AIEE по техническим операциям для презентации на летнем общем собрании AIEE, Атлантик-Сити, Нью-Джерси, 15–19 июня 1953 г.
• "Натали Форд Вейтч, Паоли, Пенсильвания". Legacy.com (некролог). 2005-05-13. Архивировано из оригинала 2019-08-07 . Получено 2019-08-07 .
• Вейтч, Эндрю Ф. (2012-10-01) [ок. 2010-х]. "Личная переписка и комментарии Эдварда Уэстбрука Вейтча в его последние годы". Архивировано из оригинала 2019-08-07 . Получено 2019-08-07 .(Примечание. Это самостоятельно опубликованный первоисточник, но его стоит упомянуть здесь по историческим причинам.)