1. Послание кодируют не для того, чтобы его мог прочитать только заданный получатель, но для того, чтобы оно могло быть расшифровано неопределённым количеством неизвестных получателей. В связи с этим послание кодируют таким образом, чтобы при его расшифровке использовались фундаментальные принципы, не зависящие от культуры.
2. Послание закодировано двумя символами (битами). Для того чтобы понять, действительно ли это сигнал от братьев-по-разуму, или просто всплеск радиоактивности близлежащего пульсара, необходимо применить понятие информационной энтропии. Если энтропия сообщения находится в некотором интересном интервале, то есть некоторая уверенность в том, что сигнал имеет искусственное происхождение.
3. Если послание прошло энтропийный тест, то его необходимо проверить на тест простых чисел, а именно количество символов в сообщении (в данном случае бит) должно представлять собой число, у которого ровно 2 простых делителя. Это значит, что все символы сообщения можно расположить в прямоугольную матрицу двумя способами (
x * y или y * x, где x и y — простые делители длины последовательности сигналов). Далее получившиеся матрицы рассматриваются на предмет наличия в них осмысленных изображений.Все эти пункты достаточно легко автоматизировать. Для этого можно написать программу на функциональном языке высокого уровня Haskell (а вы думали, на каком языке программирования я бы ещё ог написать программу). Что ж, это сделать несложно. Всё данное сообщение и представляет собой такую программу. Его можно полностью скопировать в файл
LHS и выполнить в каком-нибудь GHCi.Для начала необходимо объявить начало модуля. Это просто, как обычно:
> module Main where
Теперь надо подключить пару модулей, из которых будут взяты некоторые полезные для проекта функции (чтобы не писать их самостоятельно). Во-первых, это функция
intercalate из модуля Data.List. Она сшивает списки из заданного списка, разделяя их заданным списком (другими словами, она будет использоваться для отображения прямоугольных матриц). Ещё одна полезная функция — primeFactors из модуля Data.Numbers.Primes, которая предназначена для факторизации заданного числа. Подключение просто:> import Data.List (intercalate) > import Data.Numbers.Primes (primeFactors)
Последний модуль не входит в стандартную поставку. Однако его можно легко скачать и установить с помощью утилиты
Cabal, которая входит в состав поставки Haskell Platform. Для этого в консоли необходимо последовательно выполнить:cabal update cabal install primes-0.2.0.0
Далее. Имеет резон написать несколько функций для отображения результатов. В качестве результата планируется получить прямоугольную матрицу битов. Сами биты можно закодировать при помощи специального типа, для которого сразу же определить экземпляр класса
Show для отображения в виде строки:> data Bit = O | I > instance Show Bit where > show O = "." > show I = "O"
После этого сами функции, которые выводят матрицу в строку и на экран. Функции полиморфны, им безразлично, какого типа будут элементы матриц. Главное, чтобы эти элементы могли бы быть отображены в виде строк. Первая функция получает на вход матрицу в виде списка списков и преобразует её в строку как раз при помощи функции
intercalate, которая прореживает элементы входного списка символом '\n. Вторая функция предназначена для преобразования входной последовательности бит в матрицу и вывода её уже на экран (то есть в монаде IO):> showMatrix :: Show a => [[a]] -> String > showMatrix = (intercalate "\n") . map (concatMap show) > putMatrix :: Show a => Int -> [a] -> IO () > putMatrix x l = (putStrLn $ showMatrix $ divideList x l) >> putStrLn "" > where > divideList _ [] = [] > divideList i ls = let (y, ls') = splitAt i ls > in y : divideList i ls'
Теперь пришло время вычислительных функций. Для начала функции, которые вычисляют информационную энтропию сообщения. Функция
entropy получает на вход последовательность сигналов и возвращает значение энтропии для неё. Функция maxEntropy возвращает максимальное значение энтропии для алфавита из заданного количества символов (такое максимальное значение получается тогда, когда на вход функции entropy подаётся сообщение, состоящее из одинакового количества сигналов каждого возможного типа). Функция maxEntropy предназначена для проверки первого критерия.> entropy :: Eq a => [a] -> Double > entropy l = (0 -) $ sum $ map (pLog $ length l) $ frequency l > where > pLog s (x, n) = p * logBase 2 p > where > p = fromIntegral n / fromIntegral s > maxEntropy :: Int -> Double > maxEntropy n = entropy [1..n]
Вспомогательной функцией является следующая. Для заданного списка она возвращает список пар, первым элементом которых являются символы исходного списка, а вторым — количества проявлений соответствующих символов в исходном списке. Предназначена для расчёта частных вероятностей при вычислении энтропии сообщения.
> frequency :: Eq a => [a] -> [(a, Int)] > frequency = frequency' [] > where > frequency' l [] = l > frequency' l (x:xs) = frequency' (corrector x l) xs > > corrector x [] = [(x, 1)] > corrector x ((x', n):xs) = if x == x' > then (x, n + 1):xs > else (x', n):(corrector x xs)
Ещё одна вспомогательная функция, вернее даже предикат. Предназначен для понимания того, входит ли заданное число в заданный же интервал. Легко полиморфно:
> inRange :: Ord a => a -> (a, a) -> Bool > inRange i (x, y) = (i >= x) && (i <= y)
Наконец, кодирование входного сигнала и пара функций для его обработки:
> inputData :: [String]
> inputData = ["(((((()()()()(((((((((((()()((((()()((((((()(()((()((()((()(()())(()()()()()()()",
> "()()(()(()((((((((((((((((((((((((((((((((((((())((((((((((((((((((())()((((((((",
> "((((((((((())()(((((((((((((((((()()()(((((((((((((((((()))))(((((((((((((((((((",
> "((((((((((((())(((()))((())(((())((()((((((((((((())(()(((())()((())((())(((())(",
> ")()))))()))))()))))()))))(((((((((((((((((((((((((()((((((((((((((((()((((((((((",
> "(((((((((((((((((()((((((((((((((((())))))((((((((((((()))))((((((((((((((((((((",
> "((())(((())(((()))((())((()((((((()((((((((()(((())()(((())((()))(())()()))))())",
> ")))()))))()))))(((((((((((((((((((((((((()(((((())((((((((()((((((((((())(((((((",
> "(((((((()((((())(((((((((())))))((((())(((((()))))(((((((((())((((((((((((()((((",
> "(((()(((((((()((((()(((((())((((((()((((((())(((())(((((()(((((((((())((()(((())",
> "((((((((((((((())(())((((((((((((())((()(((())((((((((())(((())(((((()((((((()((",
> "(((()(((((((()((((()((((((())(((((((()((()(((((((())(((((((()((()((((((((()(((((",
> "(()((((()((((((()((((((()((((((()(((((((((((())((((((((())(((((((())((((((((()((",
> "()))()())((((((((((()((((((()(((((((((((((()((((()))))(((((((((((()(((()()))()((",
> ")())())(((((()(()))(()(()))))))()))(((()))((((())()))((((((((()()((((()))())(()(",
> "((((()()((((())))))(()(((((()()((((())(((((()((((())())(((((((((((((((((((((((((",
> "(((((((((()))((((()(((((((((((((()))()()((()()()()()()(()))((((((((()()()()(((((",
> "((((((((((()()(((((((((((((()))))(((((((((((((((()))))))))(((((((((((()))(((((((",
> ")))((((((((())((((((((((())((((((())()((((((((()())((((())(())((((((())(())(((()",
> "((()()((((()()((()(((()((()(()((()(()((()(((((((()((()()((()(((((((((((()(((()((",
> "(()(((((((((((()((((((((()(((((((((((((()(()()((((((((((())))(()))))()(())))((("]
> decodeBits :: (Char -> Bit) -> String -> [Bit]
> decodeBits = map
> mapping :: Char -> Bit
> mapping '(' = O
> mapping ')' = I
> mapping _ = error "Illegal character in input sequence."
Функция
decodeBits является синонимом прекрасной функции map для специального случая, который рассматривается в этой заметке. Она будет работать с функциями типа mapping, которая преобразует символы входной строки в определённый ранее тип битов. Последняя функция написано несколько грязно (использование функции error), но для целей исследования сойдёт, ибо во входной последовательности имеются только обрабатываемые символы. Шумов нет.И, наконец, главная функция
main. Она тестирует входной сигнал двумя тестами и выводит два возможных результата на экран, если оба теста успешно пройдены. Тоже не очень сложно:> main :: IO () > main = do let iData = concat inputData > ntr = entropy iData > maxNtr = maxEntropy $ length $ frequency iData > if ntr `inRange` (0.2 * maxNtr, 0.8 * maxNtr) > then do let pf = primeFactors $ length $ iData > if length pf == 2 > then do let x:y:_ = pf > bits = decodeBits mapping iData > putMatrix x bits > putMatrix y bits > else putStrLn "FIASCO: Input sequence doesn't pass the primes test." > else putStrLn "FIASCO: Input sequence doesn't pass the entropy test." > return ()
В результате на экране консоли будут получены два изображения:
......O.O.O.O.......... ..O.O.....O.O.......O.. O...O...O...O..O.OO..O. O.O.O.O.O.O.O.O..O..O.. ....................... ............OO......... ..........OO.O......... ..........OO.O......... .........O.O.O......... .........OOOOO......... ....................... OO....OOO...OO....OO... O.............OO..O.... OO.O...OO...OO....OO.O. OOOOO.OOOOO.OOOOO.OOOOO ....................... ...O.................O. ....................... ....O.................O OOOOO.............OOOOO ....................... OO....OO....OOO...OO... O.......O.........O.... OO.O....OO...OOO..OO.O. OOOOO.OOOOO.OOOOO.OOOOO ....................... ...O......OO.........O. ..........OO........... ....O.....OO..........O OOOOO.....OO......OOOOO ..........OO........... ..O........O........O.. ...O......OO.......O... ....OO....OO......O.... ......OO...O....OO..... ..........OO..OO....... ......OO...O....OO..... ....OO....OO......O.... ...O......O........O... ..O.......OO........O.. .O........OO........O.. .O.........O.......O... ..O.......O.......O.... ...O............OO..... ....OO........OO....... ..O...OOO.O.OO......... ..O.......O............ ..O.....OOOOO.......... ..O....O.OOO.O..O.OO.OO ......O..OOO..O..OOOOOO O.OOO....OOO.....OO.OOO .........O.O.....OOO.OO ..O......O.O.....OOOOOO ..O......O.O.....OO.... ..O.....OO.OO.......... ....................... ..OOO.....O............ ..OOO.O.O...O.O.O.O.O.O ..OOO.........O.O.O.O.. ..............O.O...... ........OOOOO.......... ......OOOOOOOOO........ ....OOO.......OOO...... ...OO...........OO..... ..OO.O.........O.OO.... .OO..OO.......OO..OO... .O...O.O.....O.O...O... .O...O..O...O..O...O... .....O...O.O...O....... .....O....O....O....... .....O.........O....... .......O..O.O.......... .OOOO..OOOOO.O..OOOO...
и
......O.O.O.O............O.O.....O.O.......O..O...O...O...O..O.OO..O.O.O. O.O.O.O.O.O..O..O.....................................OO................. ..OO.O...................OO.O..................O.O.O..................OOO OO................................OO....OOO...OO....OO...O.............OO ..O....OO.O...OO...OO....OO.O.OOOOO.OOOOO.OOOOO.OOOOO.................... ......O.................O............................O.................OO OOOO.............OOOOO.......................OO....OO....OOO...OO...O.... ...O.........O....OO.O....OO...OOO..OO.O.OOOOO.OOOOO.OOOOO.OOOOO......... .................O......OO.........O...........OO...............O.....OO. .........OOOOOO.....OO......OOOOO..........OO.............O........O..... ...O.....O......OO.......O.......OO....OO......O..........OO...O....OO... ............OO..OO.............OO...O....OO.........OO....OO......O...... .O......O........O.....O.......OO........O...O........OO........O...O.... .....O.......O.....O.......O.......O.......O............OO.........OO.... ....OO.........O...OOO.O.OO...........O.......O..............O.....OOOOO. ...........O....O.OOO.O..O.OO.OO......O..OOO..O..OOOOOOO.OOO....OOO.....O O.OOO.........O.O.....OOO.OO..O......O.O.....OOOOOO..O......O.O.....OO... ...O.....OO.OO...................................OOO.....O..............O OO.O.O...O.O.O.O.O.O..OOO.........O.O.O.O................O.O............. .OOOOO................OOOOOOOOO............OOO.......OOO.........OO...... .....OO.......OO.O.........O.OO.....OO..OO.......OO..OO....O...O.O.....O. O...O....O...O..O...O..O...O........O...O.O...O............O....O....O... .........O.........O..............O..O.O...........OOOO..OOOOO.O..OOOO...
Похоже, что первое изображение явно содержит что-то осмысленное, в то время как второе — равномерный шум. И тут возникает несколько вопросов, как технического, так и методологического характера, которые и хотелось бы обсудить в комментариях с вами, мои уважаемые читатели. Итак:
1. С технической точки зрения функцию
main можно переписать так, чтобы она получала входную последовательность сигналов из некоторого файла. Это несложно (пара строк). Другое дело, что в ней же можно вставить третий тест, который будет выбирать из двух прямоугольников только тот, в котором есть нечто осмысленное (если такой вообще имеется). Какими могут быть формальные критерии такого отбора?2. И методологическая проблема. Вот мы выбрали первое изображение, на котором, вроде бы, что-то даже изображено (кстати, это послание с телескопа Аресибо, которое ушло в космос с Земли ещё в 1974 году в направлении звёздного скопления М13). Как теперь проинтерпретировать это сообщение? Как быть, какую методологию расшифровки принять к действию? Что дальше?







