Содержание к диссертации
Введение
1. Современные методы анализа и испытаний СЖАТ 8
1.1. Задачи анализа и испытаний СЖАТ 8
1.2. Характеристика временных свойств современной микроэлектронной аппаратуры 16
1.3. Сертификационные испытания СЖАТ 22
1.4. Выводы 30
2. Методы обнаружения временных задержек 31
2.1. Модели временных задержек в логических схемах 31
2.2. Виды тестов временных задержек 37
2.3. Способы тестирования и обнаружения временных задержек 44
2.4. Выводы и постановка задачи диссертации 55
3. Матричные методы анализа неисправностей типа «временная задержка» 57
3.1. Матричные модели логических схем 57
3.2. Алгоритмы преобразования МО 65
Алгоритмы построения сокращенной ЭНФ для соседних тестов 69
3.3.1. Правила подстановки значений в ТМО 69
3.3.2. Вычисление сокращенной ЭНФ по ТМО 74
3.4. Теоремы анализа сокращенных ЭНФ 81
3.5. Теоремы анализа сокращенных ЭНФ для несоседних тестов 94
3.6. Анализ несоседних тестов 96
3.7. Выводы 105
4. Исследование отношений между временными задержками и отказами в контактных схемах 106
4.1. Алгебраический метод вычисления тестов для временных задержек 106
4.2. Вычисление тестов для временных задержек через тесты для контактных схем 117
4.3. Тесты временных задержек для особенных классов схем 123
4.3.1. Бесповторные схемы 123
4.3.2. Монотонные схемы 124
4.3.3. Линейные схемы 128
4.4. Метод определения тестируемости временных задержек в комбинационной схеме 134
4.5. Выводы 140
5. Методика испытаний аппаратуры СЖАТ для временных задержек 141
5.1. Методы контроля и измерения параметров электронной аппаратуры СЖАТ 141
5.2. Способы введения временных задержек в модель логической схемы 147
5.3. Моделирование схем, преобразованных в эквивалентное дерево 151
5.4. Моделирование задержек в триггерных схемах 156
5.5. Моделирование узлов АБ-ЧКЕ 161
5.6. Выводы 176
Заключение 182
Список литературы
- Характеристика временных свойств современной микроэлектронной аппаратуры
- Способы тестирования и обнаружения временных задержек
- Алгоритмы построения сокращенной ЭНФ для соседних тестов
- Тесты временных задержек для особенных классов схем
Введение к работе
В последние годы на железнодорожном транспорте России происходит масштабное перевооружение хозяйства СЦБ современными системами и устройствами автоматики и телемеханики. Руководством ОАО «РЖД» и департамента СЦБ поставлена задача широкого внедрения на сети дорог микропроцессорных и компьютерных систем управления и контроля за движением поездов. Такого рода устройства позволят повысить пропускную способность различных устройств железнодорожного транспорта, оптимизировать процесс технического обслуживания устройств, снизить затраты на капитальное строительство и эксплуатационные расходы.
Стремительное развитие микропроцессорных и компьютерных систем железнодорожной автоматики и телемеханики обусловлено достижениями отечественных инженеров-создателей таких систем, базирующимися на успехах современной микроэлектроники - бурно развивающейся отрасли мировой науки и техники.
Подмечено, что для нормального развития отрасли полупроводниковых устройств количество логических функций на микросхеме удваивается каждые 1,5...2 года. При этом скорость обработки электрических сигналов удваивается каждые 1,5...2 года.
Современные микросхемы содержат более 10 транзисторов в кристалле
и, по оценкам специалистов, это число в ближайшее время увеличится в 10 раз.
Уже появились процессоры с тактовой частотой 4,4 ГГц. В ближайшей пер
спективе появление процессоров с тактовой частотой 10 ГГц. Дальнейшее
увеличение тактовой частоты связано с проблемами внутренних соединений:
скорость распространения логического сигнала через элементы становится со
измеримой со скоростью распространения по линиям связи.
Таким образом, дальнейшее развитие современной микроэлектроники характеризуется:
-постоянным увеличением тактовой частоты работы устройств - числом выполняемых элементарных операций за единицу времени;
- постоянным уменьшением размеров отдельных элементов.
Все это порождает зависимость нормальной работы устройств от скорости распространения сигналов между отдельными элементами или частями схем.
С увеличением быстродействия схем и тактовой частоты их работы становится более вероятным влияние временных отклонений на правильную работу аппаратуры. Наряду с константными неисправностями в микроэлектронных логических схемах могут возникать неисправности типа «временная задержка» (ВЗ) распространения логического сигнала, обнаружение которых является важной областью в тестировании микроэлектронных схем. Особенностью ВЗ по сравнению с другими видами отказов является то, что они не нарушают логическую структуру схемы и в то же время приводят к ошибочным результатам вычислений.
Как и в случае «традиционных» отказов такие ошибочные результаты вычислений могут приводить к нарушениям нормальной работы отдельных устройств или систем в целом, и, как следствие, к задержкам в графике движения поездов, уменьшению пропускной способности, сбоям в технологическом процессе работы железнодорожного транспорта. В отдельных случаях нарушения работы устройств автоматики могут приводить к опасным отказам.
Отсюда следует необходимость диагностики отказов типа ВЗ. Тестирование ВЗ в логических схемах - новая развивающаяся отрасль технической диагностики. В настоящий момент остаются нерешенными многие аспекты как в теории тестирования ВЗ, так и практического применения теоретических результатов. Развитие интегральной схемотехники ставит в этой области новые задачи. Поэтому актуальными являются исследования новых направлений и методов обнаружения ВЗ, синтеза легкотестируемых схем. Важным является получение доказательств общих тестирующих свойств различных видов тестов.
Анализ логических схем с точки зрения временных нарушений является также важным элементом тестирования и сертификационных испытаний схем железнодорожной автоматики, поскольку ВЗ в работе аппаратуры могут приво-
дить к искажениям вычислительных и логических процедур с нарушением безопасности.
Решение обозначенных проблем позволит создавать и производить устройства и системы железнодорожной автоматики, защищенные от опасного воздействия неисправностей типа ВЗ, что, в свою очередь, должно плодотворно сказаться на их безопасности и безотказности.
Характеристика временных свойств современной микроэлектронной аппаратуры
В последние несколько десятков лет отрасль полупроводниковых устройств отличается высокими темпами развития, которые обуславливаются, в том числе, постоянным сокращением минимального размера компонентов интегральных схем и, вследствие этого, плотностью упаковки логических элементов на кристалле.
Подмечено [1], что для удовлетворения спроса потребителей, т. е. нормального развития отрасли количество логических функций на микросхеме удваивается каждые 1,5...2 года. Точно также увеличивается скорость обработки электрических сигналов или число команд, выполняемых процессором в секунду - удваивается каждые 1,5...2 года. Современные СБИС, выполненные по технологии КМОП, на сегодняшний день содержат более 108 транзисторов в кристалле и, по оценкам специалистов, это число в ближайшее время увеличится в 10 раз [4, 5]. Уже выпускаются процессоры Pentium IV с тактовой частотой 4,4 ГГц. В ближайшей перспективе появление процессоров с тактовой частотой 10 ГГц. Дальнейшее увеличение тактовой частоты связано с проблемами внутренних соединений: скорость распространения логического сигнала через элементы становится соизмеримой со скоростью распространения по линиям связи [33].
Тенденции изменения степени интеграции СБИС в период с середины 1990-х гг. до 2010 г. представлены на рис. 1.9. Верхней кривой на графике соответствует динамика развития однородных схем - элементов памяти динамических ОЗУ (ДОЗУ). Нижняя кривая отражает развитие неоднородных схем -микропроцессоров [6].
Основными факторами повышения интеграции СБИС являются следующие: - уменьшение топологических размеров элементов; - увеличение плотности размещения элементов на кристалле; - совершенствование схемотехники и архитектуры; - уровень развития полупроводникового производства.
На рис. 1.10 графически отражены тенденции роста локальной тактовой частоты на микросхеме на ближайшее десятилетие по данным International Technology Roadmap for Semiconductors (ITRS) - ведущей в мире организации, объединяющей разработчиков полупроводниковой техники. Тактовая частота, достижимая в каждом из поколений продуктов, связана с производительностью транзисторов на микросхеме (локальная тактовая частота) и становится все существенней по мере все более полного использования особенностей микроархитектуры [1].
Сравнение параметров традиционной релейной техники и современных электронных элементов, применяемых в различных СЖАТ, составленное по данным [4, 5, 6, 39, 52, 59, 69, 73], приведено втабл. 1.1. 80786 Тенденции изменения степени интеграции СБИС Таблица 1.1 Сравнение параметров элементов, применяемых в различных СЖАТ № п/п Тип элемента Интенсивность отказов, 10-6ч- Плотностьупаковки,элемент/см3 Потребляемаямощность,мВт Задержка распространения сигнала, мкс 1 реле электромагнитные 0,17 0,001...0,1 103 20-Ю3 2 однокристальные ЭВМ и микропроцессоры 1,00 2 107 5...500 0,003...2,0 3 полупроводниковые интегральные схемы 0,45 2...105 0,5...100 0,0004...1,0 4 транзисторыбиполярные иполевые 0,29 0,03...2,0 50...500 0,5...20 5 оптопары 0,38 0,5...200 6...300 0,01...1000 с зо о га . Тенденции роста тактовой частоты работы микросхем
Общая задержка сигналов при преобразовании информации складывается из задержек сигналов в логических элементах и времени распространения сигналов в линиях связи. Например, при скорости распространения сигнала по линии связи =15...20 см/нс межэлементная связь длиной 30 см дает задержку сигнала в 1,5...2 не, что сопоставимо с задержкой быстродействующего логического элемента. Реальные потери быстродействия из-за задержек сигналов в линиях связи довольно значительны, например, в вычислительных машинах фирмы IBM время распространения сигнала по линиям межэлементных связей составило 70...80% длительности цикла. Поэтому попытки уменьшить время распространения сигнала по логическим элементам были предприняты уже в 90-х гг. XX в. [85] и не прекращаются до сих пор.
Распространение логического сигнала в современных схемах с ростом частоты усложняется также из-за увеличения емкостного и индуктивного связывания, которое снижает пиковые скорости и порождает временную неопределенность и потенциальные логические ошибки. Дополнительное затухание сигналов связано с индуктивностью пучков проводов и впаев при монтаже.
Существует несколько путей решения проблемы: использование малого логического перепада для передачи по линиям связи; уменьшение площади и входной емкости логических элементов, создание оптимальных внутренних структур СБИС, поиск новых материалов, совершенствование технологии производства СБИС [4, 5, 33] (рис. 1.11). Пути развития микроэлектроники Малый логический перепад Уменьшение площади и входной емкости логических элементов Создание оптимальных внутренних структур Поиск новых материалов Совершенствование технологии производства Пути развития современной микроэлектроники
Использование малого логического перепада позволяет снизить влияние повышенной емкости элементов и индуктивные влияния от параллельных цепей, проходящих в шлейфах. Фирма Intel уже представила на конференции производителей электронных устройств International Electronic Device Manufacturers в Сан-Франциско прототип транзистора, в котором минимальный размер элементов составляет 0,03 мкм, что позволит создавать чипы с 400 миллионами транзисторов, работающих с тактовой частотой 10 ГГц. При этом напряжение питания не превысит 1 В. Что касается компенсации вредных эффектов вызванных монтажом, то для их уменьшения производители рассматривают возможность в будущем присоединять микросхемы напрямую.
Меняются и размеры внутренних элементов и внутренняя структура микросхем. До 2001 г. процессоры Pentium IV производились по 0,18-мкм технологии. Каждый такой процессор содержал по 42 млн. транзисторов и имел тактовую частоту 1,5 ГГц. К концу 2001 г. фирма Intel перешла на 0,13-мкм технологию в массовом производстве, в 2003 г. - на 0,10-мкм технологическую норму, в ближайшее время ожидается переход на 0,07-мкм технологию. Intel планирует уменьшать размер транзисторов в своих процессорах на 30% каждые два года. Примеры устройств и компонентов вычислительных систем, произведенных пот. н. наноразмернойтехнологии, приведены в [80, 81, 82, 83, 92].
Развивается направление, связанное с применением новых материалов при производстве микросхем и совершенствованием технологии.
Происходит замена алюминиевых проводников в микросхемах на медные, имеющие меньшее удельное сопротивление. Большая часть работ [4, 5] посвящена материалам, применяемым при производстве БИС. В [78] предложен быстродействующий элемент памяти (со временем переключения 10"12...10"10 с) на основе периодической наноразмерной БІ/СаРг-структурьі.
Изменяется и технология производства микросхем. Изменения касаются как внутренней структуры и архитектуры, так и применения новых технологических процессов при производстве [6, 7, 33, 84, 95].
Способы тестирования и обнаружения временных задержек
Самопроверяемые (самотестируемые) устройства также позволяют при определенном построении резко уменьшать количество необходимых для покрытия всех неисправностей тестовых векторов и, как следствие, уменьшать время необходимое для тестирования схем. В [97] описывается генератор тестов MISR. Для тестирования схемы с п входами и тестовыми парами требуется элементов памяти и к -2" тактов работы схемы для генерации всех тестовых последовательностей. Причем к &к. В [93] приведены решения, позволяющие применить самопроверяемые узлы в схемах со сканированием константных неисправностей.
Говоря о программных способах тестирования схем на наличие ВЗ, можно отметить, что современная наука уделяет большое внимание синтезу легко-тестируемых с точки зрения ВЗ схем,
Например, в [90] предложен подход к синтезу многоуровневых комбинационных схем, в которых все пути являются не менее, чем достоверно нероба-стно тестируемыми. Схемы синтезируются автоматически, в соответствии с определенными требованиями. При этом в работе показывается, что достоверное неробастное тестирование, в отличие от робастного, предоставляет широкие возможности для развития эффективных процедур синтеза тестируемых с точки зрения ВЗ схем и позволяет тестировать неисправности схемы меньшим количеством тестовых комбинаций. В работе также доказаны теоремы, определяющие необходимые и достаточные условия для достоверной неробастной тестируемости путей произвольной комбинационной схемы. В качестве математической модели путей комбинационной схемы используется ЭНФ.
Классические условия тестирования ВЗ определены для схем содержащих только простые элементы (И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ). Однако, большинство современных реализаций функций, использующих КМОП-технологию, содержат множество сложных элементов (например, И-ИЛИ-НЕ). Как правило, для тестирования ВЗ такие схемы моделируются таким образом, что для реализации функции используются только простые элементы. Проблемам, возникающим в этой связи, посвящена работа [102]. В ней определены подходы к тестированию схем на сложных элементах, смоделированных с использованием только простых, введены понятия г-робастного теста и г-робастной тестируемости путей в схемах на сложных элементах, определены необходимые и достаточные условия r-тестируемости схем.
Большинство теоретических методов диагностирования ВЗ сводится к сужению списка путей схемы, подлежащих тестированию на наличие ВЗ.
Для того чтобы гарантировать отсутствие в комбинационной логической схеме неисправностей типа ВЗ, необходимо протестировать все пути, либо все элементы, что практически невозможно, поскольку число путей может расти экспоненциально от числа элементов схемы, а тестирование отдельных элементов интегральных схем затруднено конструктивными особенностями. В этой связи большое внимание уделяется нахождению оптимальных методов тестирования схем.
Анализ путей комбинационных логических схем показывает, что схемы могут содержать избыточные пути, по которым логические сигналы не распространяются, то есть такие пути, которые ни при какой тестовой последовательности не становятся чувствительными. Очевидно, такие пути не могут вызвать ВЗ на выходе схемы, хотя и могут иметь временные отклонения. Такие пути не требуется тестировать. Выявление таких путей позволяет сократить список путей, которые необходимо тестировать.
Существуют также нетестируемые пути схемы. В [100] описывается метод обнаружения нетестируемых путей в комбинационных логических схемах (метод поиска нетестируемых сегментов). Идея метода заключается в том, что тестируемая схема разделяется на сегменты, в которых по определенным правилам отыскиваются нетестируемые линии (фрагменты). В [100] доказано, что если некоторый фрагмент некоторого пути схемы не может быть чувствительным ни при каких комбинациях входных наборов (unsensitizable path - UP), то все пути схемы, включающие этот фрагмент, так же являются UP, т. е. являются нетестируемыми.
Далее все пути схемы, проходящие через найденную нетестируемую линию (фрагмент) отмечаются как нетестируемые, что позволяет исключить их из дальнейшего рассмотрения, экономя тем самым время и ресурсы, затрачиваемые на процедуру тестирования.
Алгоритмы построения сокращенной ЭНФ для соседних тестов
Теперь по ТМО можно вычислить СЭНФ Для чего воспользуемся методикой, изложенной в [65]. Вычисления начинаются с последней строки. При этом применяются следующие правила. 4. В последней строке ТМО могут быть записаны следующие отношения: 4.1. Если в последней строке записано отношение а=0, то СЭНФ=0. 4.2. Если в последней строке записано отношение а -+1, то СЭНФ=1 4.3. Если в последней строке записано отношение а=\ или си-+0, то СЭНФ а 5. Если в строке записано некоторое отношение и путь а — стабильный, то такая строка при вычислениях СЭНФ не учитывается. 6. Если в строке записано отношение а++Ь, при этом пути а и Ъ - нестабильные, то в выражении вычисляемой СЭНФ ЭТО отношение заменяется дизъюнкцией a v Ь. 7. Если в строке записано отношение а=Ъ, при этом пути а и b — нестабильные, то в выражении вычисляемой СЭНФ ЭТО отношение заменяется конъюнкцией а лЬ. 8. Если в строке записано отношение а=\ или з -»0, при этом путь а - нестабильный, то в выражении вычисляемой СЭНФ путь а остается без изменений. 9. Если в строке записано отношение а -»-1, при этом путь а - нестабильный, то в выражении вычисляемой СЭНФ ЭТО отношение заменяется на 1. 10. Если в строке записано отношение д-0, при этом путь а - нестабиль ный, то в выражении вычисляемой СЭНФ ЭТО отношение заменяется на 0.
Полученное выражение приводится к ДНФ. Нулевые конъюнкции устраняются. Получается выражение СЭНФ
Аналогичный результат можно получить и подстановкой в эквивалентную контактную схему (см. рис. 3.2) значений входных переменных. Для наглядности заменим замкнутые контакты шунтами, а разомкнутые - обрывами. При этом схема приобретает вид, показанный на рис. 3.15. После дальнейшего преобразования, суть которого сводится к удалению разомкнутых и зашунтиро-ванных контактов, схема приобретает вид, соответствующий выражению (3.4) и изображена нарис. 3.16.
Минимизированная сокращенная эквивалентная контактная схема Составим ТМО для всех других путей схемы и протестируем их соседними тестами. Результаты трансформации МО, произведенной по предложенному выше алгоритму представлены в приложении Б.
В процессе тестирования логических схем часто бывают необходимы значения обратной функции. Обратную 0СЭНФ легко получить из ТМО, заменяя знаки «=» на и наоборот, а так же инвертируя пути схемы. Пример обратной ТМО приведен в табл. 3.8.
В табл. 3,9 сведены результаты расчета FC3uo и ОСЭНФ ДЛЯ всех путей схемы, рассматриваемой на рис. 3.1.
В [89] предложены теоремы позволяющие анализировать некоторые частные случаи Fc3H0- Однако они не позволяют решать задачи анализа получаемых в результате расчетов произвольных видов /ЧЭНФ- Поэтому ниже приводится решение в общем виде. Рассмотрим схему на рис. 3.17
Будем называть двоичный набор разрешенным или запрещенным, если значение функции на этом наборе равно 1 или 0. Пусть сокращенная ЭНФ получена в результате подстановки значений переменных векторной пары (V\, Уг), где V\ - разрешенный или запрещенный набор, Уг - разрешенный набор. Векторная пара (V], Уг) является соседней по переменной а. Если сокращенная ЭНФ равна константе, то векторная пара (У\, V2) не является тестом. Метод анализа сокращенной ЭНФ, которая не равна константе, заключается в подстановке в формулу Т СЭНФ значения переменной а, которое она имеет в наборе Уг. Результаты анализа определяют следующие три теоремы [62, 64].
Теорема 3.1. Если при подстановке значения переменной а в сокращенную ЭНФ все ее конъюнкции равны 1 и содержат одну и ту же букву a, то векторная пара (V\, Уг) есть робастный тест для неисправности а,-01.
Доказательство. Так как набор У2 является разрешенным и все конъюнкции Т СЭМФ содержат букву ah то набор У\ является запрещенным. Тогда изменение сигнала 0-И на выходе схемы произойдет только в том случае, если произошло изменение сигнала 0-И вдоль пути щ. Поэтому задержка изменения сигнала 0-И вдоль пути а, вызовет задержку такого же изменения на выходе схемы независимо от наличия других временных неисправностей в схеме.
Тесты временных задержек для особенных классов схем
Линейная схема широко используется в дискретных системах и системах передачи информации для контроля четности двоичных векторов. Относительно константных неисправностей эта схема одна из самых легко-контролируемых. В работе [67] показано, что одиночный тест линейной схемы содержит четыре набора независимо от числа переменных и, а полный тест -п+2 набора. Это свойство определяется «прозрачностью» элемента М2 при трансляции искажения входных сигналов. Например, на рис. 4.12 искажение сигнала на входе а транслируется на выход/и при значении 6=0 (по чувствительному пути 1-3) и при значении Ь=\ (по чувствительному пути 2-3). Иными словами, изменение сигнала на входе х( схемы вызывает изменение сигнала на выходе/при любых значениях остальных переменных xvx2,...,xi_l,xi+l,...,хп. Это означает, что всегда создается чувствительный путь от входа X; до выхода / Рассмотрим теперь свойства линейной схемы при обнаружении ВЗ путей. Свойство 4.4. Минимальное число соседних робастных тестов для обнаружения временных задержек путей в линейной схеме равно 3-2" -4.
Доказательство состоит из двух частей. Сначала сформулируем алгоритм, с помощью которого строятся соседние робастные тесты для каждого пути линейной схемы, а затем найдем формулу для подсчета числа этих тестов.
Искомый алгоритм является рекуррентным. Он задает правила, по которым строится тест для схемы от п переменных, если известен тест для схемы от п \ переменной. При и=2 (рис. 4.12) схема имеет 4 пути и 8 робастных соседних тестов, которые приведены в табл. 4.6. В таблице используются следующие обозначения путей: ах = ахъ, аг — аг,г, b\ = Ы,г, Ъг -Ь1Ъ. Линейная схема при п=Ъ (рис. 4.13) имеет десять путей: аи =я]346, Й12 =Й1,3,5,б, Я21 =а2,Э,4,6, й22 =«2,3,5,6 11 = .3,4,6, Ь2 = 6і3,5,6 Ь2\ = \з,4,б &22 = 2,3,5,6, CI = С4.6, С2 С5 6 РИ этом ВОСЄМЬ Путей ПОрОЖДЭЮТСЯ ЧЄТЬфЬМЯ путями предыдущей схемы (рис. 4.12) для и=2 (т. е. для п-\) переменной. 130 Например, путь flj в схеме рис. 4.12 порождает пути ап и an в схеме рис. 4.13. Еще два пути С\ и с2 порождаются новой входной переменной с. В общем случае для подсчета числа путей Nn справедлива рекуррентная формула
В схеме рис. 4.13 каждый из десяти путей имеет робастные соседние тесты для обоих видов задержек. Эти тесты приведены в табл. 4.7.
Тесты для задержек первых восьми путей порождаются тестами предыдущей схемы путем приписывания к ним прямого и инверсного значений новой переменной. Например, тест (0, 2)={аЪ,аЬ) для задержки ах в схеме рис. 4.12 порождает два теста (0, 4)=(abc,abc) и (1, 5)=(abc,abc) для задержек a и а в схеме рис. 4.13. Так порождаются первые шестнадцать тестов в табл. 4.7. Четыре теста, для путей, связанных с последней переменной с, образуются следующим образом. В двух тестовых наборах переменной с приписывается прямое значение. При этом среди остальных переменных в одном тесте число еди 131 ниц должно быть четно (в табл. 4.7 это тест (0, \)=(abc,abc)), а в другом - нечетно (тест (2, Ъ)={аЬс,аЬс)). Аналогично образуются два тестовых набора, в которых переменной с приписывается инверсное значение.
Из описанного алгоритма следует, что каждый путь в линейной схеме имеет соседний робастный тест. В то же время, два разных пути от одного входа линейной схемы до выхода не имеют одного и того же соседнего теста. Это вытекает из очевидного факта, что один соседний тест в линейной схеме активизирует только один путь. Таким образом, минимальное число соседних роба-стных тестов линейной схемы равно удвоенному числу путей в схеме.
Теперь переходим ко второй части доказательства. Покажем, что число тестов линейной схемы равно 3-2" — 4. Воспользуемся выражением (4.14) для подсчета числа путей. При/7=2 имеем JV3=4 = 22+2 -2. При п=3 имеем Л/з = 2 2 + 2 = 2(22 + 2 -2)+2 = 23 + 22-4+2 = 23+22-2 = 10. Пусть при n=i справедливо N„ =2 +2 " -2. Покажем, что тогда при n=i+l также справедливо Nn+l = 2 + + 2 - 2.
