Клеточные автоматы в криптографии.Часть 1

Немного истории

"…Клеточные автоматы изобретались много раз под разными названиями, и несколько отличающиеся друг от друга понятия употреблялись под одним и тем же названием".

Т. Тоффоли, Н. Марголус [Tof87]

Более или менее полная история возникновения и развития теории клеточных автоматов (КлА), а также обзор их возможных приложений требует отдельной и весьма объемистой статьи. Читателю, заинтересованному историей клеточных автоматов, можно предложить обзоры [Sar00], [Sut09] и книги [Bur70], [Mai07], [Mai12], [Neu66], [Tof87], [Scf08]. Здесь же мы ограничимся самыми общими историческими сведениями.

Наиболее известным и распространенным мнением является то, что создателем клеточных автоматов стал Джон фон Нейман. Более внимательное изучение истории появления этого понятия показывает, что в конце 40-х гг идея клеточного автомата, что называется, "витала в воздухе" и к числу его создателей следует причислить по крайней мере пятерых выдающихся ученых.

В 1940-е гг. Джон фон Нейман (János Lajos Neumann, 1903– 1957), будучи сотрудником Лос-Аламосской национальной лаборатории, работал над теорией самовоспроизводящихся систем [Neu66], [Bur70]. В это же время другой сотрудник той же лаборатории, Станислав Улам (Stanislaw Marcin Ulam, 1909–1984), разрабатывал математическую модель роста кристаллов [Ula62]. Обмен идеями между коллегами привел к возникновению клеточно-автоматной модели эволюции систем.

Приблизительно тогда же работавшие в Массачусетском технологическом институте (MIT) Норберт Винер (Norbert Wiener, 1894–1964) и Артуро Розенблют (Arturo Rosenblueth, 1900–1970) разработали клеточно-автоматную модель возбудимой среды для описания распространения импульсов в нервных узлах [Wie46].

Пятым "отцом" теории клеточных автоматов следует считать выдающегося немецкого инженера Конрада Цузе (Konrad Zuse, 1910–1995) – создателя первого в современном смысле программируемого компьютера Z3 (1941 г.) и первого языка программирования высокого уровня (1945 г.). Клеточные автоматы (под именем "вычисляющиеся пространства") рассматривались им в качестве возможной архитектуры вычислительных систем. В силу понятных политических и идеологических соображений Конрад Цузе не получил всемирной славы как "отец кибернетики", что, однако, не умаляет его заслуг.

В 1969 г. К. Цузе опубликовал книгу "Вычислимый космос" [Zus69], где выдвинул предположение, что по своей природе Вселенная является гигантским клеточным автоматом, а происходящие в ней физические процессы – суть производимые вычисления. В то время такой взгляд на Вселенную был шокирующим, тогда как сейчас идея вычисляющей саму себя Вселенной получила дальнейшее развитие [Ber09], [Fla98], [Ger89], [Ila02], [Kau95], [Mai12], [Pet03], [Scf08]. Книга К. Цузе положила начало так называемой цифровой физике – модному ныне направлению, относящемуся не столько к современной физике, сколько к философии.

Первая же фундаментальная книга, посвященная непосредственно клеточным автоматам, была создана по черновым записям и незавершенным статьям Дж. фон Неймана, законченным и переработанным его многолетним сотрудником А. Бёрксом (Burks A.W.), и вышла в свет в 1966 г. [Neu66].

Классические клеточные автоматы

Клеточные автоматы являются простыми моделями пространственно протяженных децентрализованных систем, состоящих из большого числа однородных составляющих компонент (клеток, ячеек), а внутреннее функционирование сводится к локальному взаимодействию между соседними компонентами [Cha97], [Cod68], [Del99], [Gan04], [Gri03], [Kar05], [Kar16], [Pre84], [Roz11], [Scf08], [Scf], [Tof90], [Tof87], [Viv03], [Бер93], [Куд90].

Классический клеточный автомат представляет собой упорядоченный набор ячеек памяти, образующих некоторую регулярную n-мерную решетку (на практике наибольшее распространение приобрели клеточные автоматы небольшой размерности – с одно- или двумерными решетками). Структура пространственной решетки зависит от формы входящих в нее ячеек. Так, например, в двумерном случае можно рассматривать ячейки прямоугольной, треугольной, шестиугольной формы (рис. 1); разумеется, возможны и иные варианты. Наибольшее внимание получили клеточные автоматы, в которых ячейки имеют квадратную форму, а сами решетки – прямоугольную.

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

Таким образом, для классических клеточных автоматов выполняются свойства:

• параллельность вычислений. Классический клеточный автомат представляет собой дискретную динамическую систему с параллельным вычислением значений ячеек памяти;
• свойство локальности. Значение каждой ячейки памяти на следующем такте работы клеточного автомата зависит только от текущих значений ячеек в некоторой ее окрестности (и, возможно, от значения самой рассматриваемой ячейки);
• свойство однородности. Решетка однородна. Правила перехода являются одинаковыми для всех ячеек клеточного автомата.

Математически клеточный автомат над множеством с d-мерной решеткой размера, окрестностью и локальной функцией связи, задающей правила перехода, определяется как конечный автономный автомат, где:

• множество внутренних состояний автомата;
• начальное состояние автомата;
• функция переходов, определяет следующее состояние автомата как функцию от текущего состояния.

При этом множество внутренних состояний представляет собой всевозможные заполнения d-мерной решетки ячеек памяти элементами множества, каждое внутреннее состояние автомата соответствует некоторому заполнению ячеек памяти, а функция переходов определяется через локальную функцию связи, когда новое заполнение каждой ячейки памяти определяется текущим заполнением ячеек, образующих ее окрестность.

В некоторых моделях решетка клеточного автомата считается бесконечной. Тогда считается, что все ячейки, кроме конечного числа, имеют в начальный момент "пустое" (нулевое) заполнение. Однако в большинстве приложений решетка клеточного автомата имеет конечные размеры. В этом случае возникает так называемая проблема краевых клеток – как задавать значения функции для ячеек, у которых отсутствует часть соседей. Чаще всего в соответствии со свойством однородности для разрешения проблемы краевых клеток противоположные края решетки клеточных автоматов отождествляются. Тогда одномерные клеточные автоматы можно представлять в виде набора ячеек памяти, объединенных в кольцо, решетку же двумерных автоматов принято отождествлять с тором (рис. 2). Реже вводится так называемая нулевая граница (Null-Boundary): значения для отсутствующих соседей полагаются равными нулю. Известны и другие варианты решения проблемы краевых клеток.

Автомат фон Неймана

Как указывалось выше, задача, которую в 40-х гг решал фон Нейман, состояла в исследовании возможности создания самовоспроизводящихся автоматов. В процессе решения он установил тесную связь самовоспроизводящихся автоматов с машиной Тьюринга – абстрактной логической конструкцией, предложенной Аланом Тьюрингом (Alan Mathison Turing, 1912–1954) в качестве идеализированной модели вычислителя. Машину Тьюринга можно представить себе в виде устройства, способного находиться в конечном числе внутренних состояний, снабженного бесконечной внешней памятью и набором инструкций, позволяющих в зависимости от данных, записанных во внешней памяти, менять свои внутренние состояния, переходить от одной ячейки памяти к другой, меняя при необходимости их содержание. Машины Тьюринга с разными наборами инструкций способны к выполнению различных задач. Достоинством машин Тьюринга является простота их устройства, однако они совершенно неэффективны даже для простейших вычислений и представляют интерес исключительно с теоретической точки зрения. Так, очень важным обстоятельством является тот теоретический факт, что существует машина Тьюринга, которая способна эмулировать работу любой другой машины Тьюринга, включая саму себя. Это так называемая универсальная машина Тьюринга, и она способна выполнять любые вычисления, которые выполнимы в принципе.

В 1952 г. фон Нейману удается решить проблему самовоспроизводящихся автоматов и построить соответствующий пример [Neu66]. Автомат фон Неймана представляет собой двумерный клеточный автомат с квадратными ячейками памяти, организованными в прямоугольную решетку, окрестность каждой клетки состоит из нее самой и четырех клеток, имеющих с ней общие границы (окрестность фон Неймана). Ячейка памяти, соответствующая клетке, может находиться в 29 возможных состояниях (включая состояние, называемое состоянием покоя). Двумерное пространство считается бесконечным, и все клетки, кроме конечного числа, первоначально находятся в "покоящемся" состоянии. Автомат задается определенным правилом взаимодействия клеток (локальной функцией связи) и конкретной исходной конфигурацией – начальным заполнением клеток.

"Самовоспроизведение" автомата фон Неймана выражается в том, что через некоторое время после начала работы на решетке присутствуют две его точные копии, в той же конфигурации, как это было в начале работы. Сам автомат сложен, для его задания требуется порядка 200 000 ячеек. Автомат фон Неймана содержит универсальный конструктор и универсальную машину Тьюринга (универсальный вычислитель), то есть способен выполнять любые вычисления. Хотя этот автомат никогда не был реализован на практике, главный итог состоял в том, что было доказано отсутствие логического противоречия в понятии "самовоспроизводящаяся машина" и продемонстрировано, что самовоспроизведение не нуждается в каких-то сверхъестественных средствах.

С тех пор как фон Нейман впервые сконструировал свой автомат, многие другие исследователи либо улучшили его оригинальную конструкцию, либо разработали альтернативные конструкции. Так, в 1968 г. Кодд (Codd E.F.) упростил конструкцию фон Неймана (в которой ячейки принимают 29 возможных состояний) и построил КлА с теми же свойствами, в котором каждая ячейка может принимать восемь состояний [Cod68]. В 1971 г. Бэнкс (Banks E.R.) [Ban71] предложил аналогичный автомат, ячейки которого могли принимать четыре состояния (см. также работы Мура (Moore E.F.) [Moo62] и Бёркса [Bur70]). В 1984 г. Лэнгтон (Langton C.) опубликовал самовоспроизводящийся клеточный автомат, состоящий из 86 клеток, принимающих восемь состояний, который, правда, не проявляет свойства универсального вычислителя, как это делали автоматы фон Неймана и Кодда, а просто воспроизводит сам себя [Lan84].

Обзор пятидесятилетнего периода исследований по самовоспроизведению автоматов можно найти в статье Сиппера (Sipper М.) [Sip98], а также в более ранних книгах Бёркса и Кодда [Bur70], [Cod68].

Дальнейшее развитие

Начиная с 60-х гг. шло активное изучение клеточных автоматов как динамических систем. Обзор результатов, полученных в этом направлении, можно найти в работе Хедлунда (Hedlund G.A.) [Hed69].

В 70-е гг. широкую известность получил двумерный клеточный автомат, известный как игра "Жизнь" (Game of Life). Игра "Жизнь" была создана в 1970 г. Джоном Конвеем (Conway J.), математиком из Кембриджского университета, и получила широкую известность после публикаций статей Мартина Гарднера (Gardner M.) в журнале Scientific American [Gar70], [Gar71], см. также [Гар72]. Исходным мотивом для создания игры "Жизнь" была попытка построить математическую модель для изучения реальных процессов, происходящих при зарождении, развитии и гибели популяции живых организмов. В 1982 г. удалось получить конфигурацию клеток (состояние), способную к самовоспроизведению. Джон Конвей также доказал, что игра "Жизнь", как и самовоспроизводящийся автомат фон Неймана, имеет мощность универсальной машины Тьюринга: любая программа, которая может быть запущена на машине Тьюринга, может быть выполнена с помощью игры "Жизнь" с соответствующей первоначальной конфигурацией состояний. Эта первоначальная конфигурация кодирует и входные данные, и саму программу, которая будет обрабатывать входные данные.

Вообще исследованию вычислительных возможностей клеточных автоматов посвящен большой цикл работ (см., например, [Del99], [Mit98], [Mor89], [Oll08], [Roz11], [Tof77]). То, что клеточные автоматы могут моделировать машины Тьюринга и, следовательно, быть универсальными вычислителями, стало ясно после того, как фон Нейман построил свой автомат, который эмулировал работу универсальной машины Тьюринга. Спустя 20 лет Смит (Smith III, A.R.) доказал, что элементарный одномерный КлА с окрестностью радиуса 1 эквивалентен машине Тьюринга [Smi71], [Smi76]. Заметим, кстати, что моделирование работы машины Тьюринга клеточным автоматом немедленно влечет за собой доказательство неразрешимости ряда вопросов, связанных с поведением КлА.

Интерес к КлА еще больше усилился в начале 80-х гг. после того, как физик Стивен Вольфрам (Wolfram S.) опубликовал в 1983 г. первую из серии статей, исследующих различные классы клеточных автоматов [Wol83]. В следующие три года он публикует работы [Wol84a], [Wol84b], [Wol84c], [Wol85], [Wol86]), делающие его известным благодаря тем идеям, которые в них развиваются. В этих работах Вольфрам делает акцент на возможности использования клеточных автоматов в качестве математических моделей физических, биологических и вычислительных систем. Аргументами служат простота их конструкции, способность к сложному поведению, а также возможность точного математического анализа их поведения [Wol94]. В 2002 г. Вольфрам публикует монографию "Новый тип науки" (A New Kind of Science [Wol02]), 1280 страниц, где наглядно демонстрирует, что клеточные автоматы, будучи достаточно простой структурой, в процессе своего функционирования могут моделировать сложное поведение совокупности различных, порой весьма сложно устроенных взаимосвязанных однородных объектов.

Нельзя сказать, что идея клеточных автоматов "перевернула мир", но она по факту нашла применение почти во всех областях современной науки. Свидетельство тому – впечатляющее количество ежегодно происходящих крупных международных конференций, посвященных КлА и смежным областям:

• International Conference on Cellular Automata for Research and Industry (ACRI) – с 1994 г.;
• International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) – с 1995 г.;
• International Conference "Advances in Information Technology" (IAIT);
• International Conference "Network and Parallel Computing" (NPC);
• International Conference on Unconventional Computation (UC).

Сейчас теория КлА является установившейся научной дисциплиной с многочисленными приложениями в очень многих областях науки ([Cha97], [Cho98], [Deu04], [Gayl96], [Gay98], [Gil99], [Gol99], [Hoe10], [Kru96], [Mai07], [OSu00], [Sce71], [Vic84], [Бер93]). Вольфрам упоминает более 10 тыс. статей, ссылающихся на его оригинальные работы по этому вопросу. Будучи математическим объектом, клеточные автоматы применимы не только в математике. Они играют важную роль в качестве моделей пространственно-распределенных динамических систем, поскольку изначально обладают рядом фундаментальных свойств, присущих физическому миру: параллелизмом, однородностью, локальностью взаимодействия. Другие свойства, такие как обратимость и законы сохранения, могут быть обеспечены надлежащим выбором локальных функций связи. Не удивительно, что КлА успешно применяются при моделировании сложных систем в биохимии и генетике, компьютерных технологиях и информатике, экономике и социологии. Это имитационное моделирование физических процессов и систем (моделирование течения жидкости, моделирование диффузионных процессов, модель Изинга), моделирование в теории хаоса и теории фракталов, биологические модели взаимодействующих клеточных систем, включая модели самовоспроизводства, моделирование городской транспортной сети и модели структурной лингвистики. Сюда же можно отнести исследования в области искусственного интеллекта, работы по созданию новых перспективных архитектур высокопроизводительной вычислительной техники, по использованию клеточных автоматов для обработки изображений и в теории помехоустойчивого кодирования. Применяются они и в криптографии.

Литература

• [Евс10] Евсютин О.О., Россошек С.К. Использование клеточных автоматов для решения задач преобразования информации // Доклады ТУСУРа. – 2010. – № 1 (21), часть 1. – с. 173–174.
• [Tof87] Toffoli T., Margolus N. Cellular automata machines: A new environment for modeling. – Cambridge, Mass.: MIT Press, 1987. [Рус. перевод: Тоффоли Т., Марголус Н. Машины клеточных автоматов: пер. с англ. – М.: Мир, 1991.]
• [Sar00] Sarkar P. A brief history of cellular automata // ACM Computing Surveys. – 2000. – vol. 32, No. 1. – pp. 80–107.
• [Sut09] Sutner K. Classification of cellular automata // Encyclopedia of Complexity and Systems Science. – Springer, 2009.
• [Bur70] Burks A.W. Essays on cellular automata. – Urban, IL: University of Illinois Press, 1970.
• [Mai07] Mainzer K. Thinking in complexity. The computational dynamics of matter, mind, and mankind. – Berlin: Springer, 2007.
• [Mai12] Mainzer K., Chua L. The Universe as automaton. – Springer, 2012. – 112 p.
• [Neu66] von Neumann, J. Theory of self-reproducing automata (edited and completed by A.W. Burks). – Urbana, IL: University of Illinois Press, 1966. – 388 p. [Рус. перевод: фон Нейман Дж. Теория самовоспроизводящихся автоматов: пер. с англ. – М.: Мир, 1971].
• [Scf08] Schiff J.L. Cellular automata. A Discrete View of the World. – A John Wiley & Sons Inc., Publication. University of Auck-land.– 2008.– 279 p.
• [Ula62] Ulam S. On some mathematical problems connected with patterns of growth of figures // Proceedings of Symposia in Applied Mathematics. – 1962. – 14. – pp. 215–224.
• [Wie46] Wiener N., Rosenbluth A. The mathematical formulation of the problem of conduction of impulses in a network of connected excitable elements, specifically in cardiac muscle // Arch. Inst. Cardiol. Mex. – 1946. – 16. – pp. 205–265.
• [Zus69] Zuse K. Rechnender Raum. – Braunschweig: Friedrich Vieweg & Sohn, 1969. [Англ. перевод: Zuse K. Calculating Space. – Cambridge, Mass.: MIT Technical Translation, 1970.]
• [Ber09] Berthold O. Computational universes. – Berlin: Humboldt Universitat zu Berlin, Institut fur Informatik, 2009. – 22 p.
• [Fla98] Flake G.W. The computational beauty of Nature. – MIT Press, 1998.
• [Ger89] Gernert D. Cellular automata and the concept of space. // Becker J., Eisele I., Mündemann, F. (eds.) Parallelism, Learning, Evolution: Proceedings of the Workshop on Evolutionary Models and Strategies/Proceedings of the Workshop on Parallel Processing: Logic, Organization, and Technology (WOPPLOT 89). – LNAI vol. 565. – Springer-Verlag, 1989. – pp. 94–102.
• [Ila02] Ilachinski A. Cellular automata: A discrete Universe (2nd ed.) – World Scientific Publ. Co., 2002.
• [Kau95] Kauffman S.A. At home in the Universe: The search for laws of self-organization and complexity. – Oxford: Oxford University Press, 1995.
• [Pet03] Petrov P. Church-Turing thesis as an immature form of Zuse-Fredkin thesis // 3rd WSEAS International Conference on Systems Theory and Scientific Computation. Special session on cellular automata and applications. – 2003.
• URL: http://digitalphysics.org/Publications/Petrov/Pet02a2/Pet02a2.htm
• [Cha97] Chaudhuri P.P., Chowdhury D.R., Nandi S., Chattopad-hyay S. Additive cellular automata, theory and applications, vol. 1. – John Wiley & Sons, 1997.
• [Cod68] Codd E.F. Cellular automata // ACM Monograph series. – New York & London: Academic Press, Inc., 1968.
• [Del99] Delorme M., Mazoyer J. Cellular automata: A parallel model // Mathematics and Its Applications, vol. 460. – Kluwer Academic Publishers, 1999.
• [Gan04] Ganguly N., Sikdar B.K., Deutsch A., Canright G., Chaudhuri P.P. A survey on cellular automata. – 2004. URL: http://www.cs.unibo.it/bison/publications/CAsurvey.pdf
• [Gri03] Griffeath D., Moore C. New Constructions in Cellular Automata. – Oxford University Press, 2003.
• [Kar05] Kari J. Theory of cellular automata: a survey // Theoretical Computer Science. – 2005. – 334. – pp. 3–33.
• [Kar16] Kari J. Cellular automata. Lecture notes. – University of Turku, Finland, 2016.
• URL: http://users.utu.fi/jkari/ca2016/
• [Pre84] Preston Jr. K., Duff M.J.B. Modern cellular automata: Theory and applications. – Plenum Press, 1984.
• [Roz11] Rozenberg, G., Baeck, T., Kok, J. (eds.) Handbook of Natural Computing. – Berlin: Springer, 2011.
• [Scf] Schiff J.L. Introduction to cellular automata. URL: http://psoup.math.wisc.edu/pub/Schiff_CAbook.pdf
• [Tof90] Toffoli T., Margolus N. Invertible cellular automata: a review // Physica D. – 1990. – 45, 1-3. – pp. 229–253.
• [Viv03] Vivien H. An introduction to cellular automata. – 2003. URL: http://www.liafa.univ-paris-diderot.fr/yunes/ca/archives/ bookvivien.pdf
• [Бер93] Беркович С.Я. Клеточные автоматы как модель реальности: пер. с англ. – М.: Изд-во МГУ, 1993. – 112 с.
• [Куд90] Кудрявцев В.Б., Подколзин А.С., Болотов А.А. Основы теории однородных структур. – М.: Наука, 1990.
• [Ban71] Banks E.R. Information and Transmission in Cellular Automata // Ph.D. diss. – Massachusetts Institute of Technology, 1971.
• [Moo62] Moore E.F. Machine models of self-reproduction // Proceedings of Symposia in Applied Mathematics. – 1962. – 14. – pp. 17–33. [Рус. перевод: Мур Э.Ф. Математические модели самовоспроизведения. В кн.: Математические проблемы в биологии: пер. с англ. – М.: Мир, 1966].
• [Lan84] Langton C. Self-reproduction in cellular automata // Physica D. – 1984. –10. – pp. 135–144.
• [Hed69] Hedlund G. Endomorphisms and automorphisms of shift dynamical systems // Math. Systems Theory. – 1969. – 3. – pp. 320–375.
• [Gar70] Gardner M. Mathematical games: The fantastic combinations of John Conway's new solitaire game «Life» // Scientific American. – 1970. – 223. – pp. 120–123.
• [Gar71] Gardner M. On cellular automata, self-reproduction, the Garden of Eden and the game of «Life // Scientific American. – 1971. – 224. – pp. 112–117.
• [Гар72] Гарднер М. Математические досуги. – М.: Мир, 1972.
• [Mit98] Mitchell M. Computation in cellular automata: A selected review // Gramss T., Bornholt S., Gross M., Mitchell M., Pellizzari T. (eds.) NonStandard Computation. – Weinheim: Wiley-VCH, 1998. – pp. 95–140.
• [Mor89] Morita K., Harao M. Computation Universality of one dimensional reversible injective cellular automata // IEICE Trans. – 1989. – E 72. – pp. 758–762.
• [Oll08] Ollinger N. Universalities in cellular automata; a (short) survey // Durand B. (ed.) Proceedings JAC 2008. – 2008. – pp. 102–118.
• [Roz11] Rozenberg, G., Baeck, T., Kok, J. (eds.) Handbook of Natural Computing. – Berlin: Springer, 2011.
• [Tof77] Toffoli T. Computation and construction universality of reversible cellular automata // Journal of Computer and System Sciences. – 1977. – 15, №2. – pp. 213–231.
• [Smi71] Smith III A. Cellular automata complexity trade-offs // Inf. Control. – 1971. – 18. – pp. 466–482.
• [Smi76] Smith III A. Introduction to and survey of polyautomata theory // Automata, Languages, Development. – Amsterdam: North-Holland Publishing Co., 1976.
• [Wol84a] Wolfram S. Cellular Automata as Models of Complexity // Nature. – 1984. – 311. – pp. 419–424.
• [Wol84b] Wolfram S. Universality and complexity in cellular automata // Physica D. – 1984. – 10. – pp. 1–35.
• [Wol84c] Wolfram S. Computation theory of cellular automata // Commun. Math. Phys. – 1984. – 96. – pp. 15–57.
• [Wol85] Wolfram S. Cryptography with Cellular Automata // Advances in Cryptology: Crypto ‘85 Proceedings. – Lecture Notes in Computer Science, vol. 218. – Springer-Verlag, 1986. – pp. 429–432.
• [Wol86] Wolfram S. Theory and applications of cellular automata: Including selected papers 1983 – 1986. – River Edge, NJ.: World Scientific Publishing Co., Inc., 1986.
• [Wol94] Wolfram S. Cellular Automata and Complexity. – Addison-Wesley, Reading, 1994.
• [Wol02] Wolfram S. A new kind of science. – Champaign, Ilinois: Wolfram Media Inc., 2002. – 1280 p.