Игры и Люди

… одетый только в халат из холщовой ткани, ходил в кабачки и к певичкам. Когда его спрашивали, почему он таков, он каждый раз открывал рот, засовывал туда кулак и не говорил. Император Лян-цзун призвал его и спросил: «Каков принцип Вашего Пути?» Гуйчжэнь ответил: «Одежда тонка — поэтому люблю вино, выпью вина и защищусь от холода, напишу картину — и расплачусь за вино. Кроме этого, ничего не умею». Лян-цзун не нашелся, что сказать…

От игрушек детства мы движемся к другим. Здесь — об этом.

Алхимия игры включает несколько ингредиентов.

Рецептура состоит из Миров, по которым можно путешествовать; не все из них достаточно хорошо населены. Дело — это Игрушка одного из миров.

Объединяя видимые и сокрытые элементы, Алхимия выступает и как самостоятельный Игрок.

Google+

Ковариационная матрица и линейная трансформация

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

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

Начнем с формирования исходных данных.

Шум и ничего более

Будем работать с двумя массивами, или как любят говорить в линейной алгебре — векторами. Переменные x0 и x1 будут представлять из себя независимые друг от друга векторы с нормальным распределением со средним 0 и дисперсией равной единице.

Почему переменных будет именно две? Только по той причине, что двумерные распределения удобно смотреть на плоском графике 🙂 Можно конечно работать и с трех- и многомерными переменными, но в этом случае наглядность может пострадать 🙂

В любом случае, этот пример можно распространить на любое количество измерений.

Я сразу сохранил два этих вектора в одной матрице x для удобства дальнейшей работы. Вот что получилось при отрисовке при N=1500 (по оси абсцисс — x0, по оси ординат — x1):

Ковариационная матрица, линейное преобразование, собственные числа, собственные векторы

Нормальное распределение двух независимых случайных переменных

Из графика видно, что наибольшая плотность вероятности действительно лежит в точке (0,0). Переменные независимы друг от друга, потому что точки с координатами (x0,x1) распределены равномерно вокруг центра.

Независимость, или некоррелированность, мы можем подтвердить также путем вычислений:

Единицы ковариационной матрицы по главной оси показывают, что переменные коррелированы сами с собой (другого и не ожидалось), а близкие к нулю значения, показывающие взаимную корреляцию говорят о том что переменные практически не зависят друг от друга.

Сделаем небольшое отступление: почему мы работаем с матрицей ковариации а не корреляции? Исторически сложилось, что корреляцию воспринимают как ковариацию, нормированную в диапазон -1, … +1. Нормировка нам не к чему, поэтому мы работаем с матрицей ковариации.

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

Линейное преобразование двух случайных векторов

Трансформацию векторов x0,x1 получают перемножением векторов на матрицу трансформации A, в результате чего получится уже новая пара векторов. Трансформация будет состоять из двух частей: поворот на угол 20°

и масштабирование с коэффициентом 4 по оси х и коэффициентом 0.5 по оси y:

В результате матрица трансформации A как произведение только что заданных матриц поворота и масштабирования будет такой:

Ну и в результате получим трансформированные векторы, чего мы и добивались:

На рисунке изображение всех значений вектора xa выделено зеленым цветом.

Ковариационная матрица, линейное преобразование, собственные числа, собственные векторы

Исходное нормальное распределение (синий цвет) и распределение после его трансформации: поворота и масштабирования (зеленый цвет)

Наше нормальное распределение деформировалось: теперь оно уже далеко не нормальное: вытянулось вдоль одной оси, сжалось вдоль другой и вдобавок еще повернуто. Но самое главное из того что произошо, это то что теперь новые векторы не являются зависимыми: например, если первый из трансформированных векторов принимает значения >10, то с высокой степенью вероятности второй вектор будет принимать значения >3, как следует из распределения. В исходном распределении такого не было: любому из значений x0 могло соответствовать любое значение x1 из области распределения.

Теперь эту зависимость отражает и ковариационная матрица:

Значение 5.135 недвусмысленно намекает на взаимосвязь между трансформированными векторами.

Здесь самое время задаться вопросом: поскольку ковариационная матрица является обобщенной характеристикой нового распределения, которое в свою очередь получено в результате трансформации A, существует ли связь между ковариацией и линейной трансформацией A?

Физический смысл ковариационной функции линейного преобразования

Заголовок отражает суть того, до чего мы докапываемся. Интуитивно понятно, что корреляция возникает в процессе изменения вектора, то есть линейной трансформации. Не вдаваясь в теорию процесса, выдадим сразу окончательный результат результат:

COV=A \cdot A^T

Картинку немного портит умножение на транспонированную матрицу линейного преобразования, но соответствие продемонстрировано однозначно.

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

Другими словами, все взаимосвязи в результате будут определяться матрицей линейного преобразования.

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

Поскольку мы занялись поисками смыслов, то самое время пристегнуть к нашей парочке ковариационная матрица — матрица линейного преобразования еще и собственные числа и собственные векторы.

В статье посвященной методу главных компонент мы занимались поиском собственных значений матрицы линейного преобразования. А что если найти собственные векторы и числа ковариационной матрицы? Сказано — сделано:

В результате получаем собственные векторы

и собственные числа:

Отрисуем их на нашем распределении красным цветом. При этом само собой масштабируем собственный вектор собственным числом:

Ковариационная матрица, линейное преобразование, собственные числа, собственные векторы

Собственные векторы линейного преобразования: показаны красным цветом

Пусть вас не смущает отсутствие стрелочки справа: она как раз находится за полем рисунка.

Собственные векторы ковариационной функции показывают направления линейной трансформации исходного распределения. Это уже второй смысл ковариационной функции нормального распределения.

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

Схемотехника: однокаскадный усилитель

Сделаем небольшую разминку: потренируемся на однотранзисторном усилителе. Когда-то чтение аналоговых схем было сродни искусству; профи по внешнему виду безошибочно определяли функционал узла. Наверное, это один из немногих оставшихся навыков, для имитации которых не получится использовать поисковые системы.

Схема на рисунке, вопрос следующий: чему равно значение выходного напряжения Uout? Заметим, что на вход мы еще ничего не подали; таким образом речь идет о задании режима работы по постоянному току, или рабочей точки транзистора.

Однокаскадный транзисторный усилитель

Предсказываю, что зреет следующий вопрос: а какой собственно коэффициент усиления у этого транзистора? Отвечаю сразу: большой. И если после такого ответа вы собираетесь настаивать на своем вопросе, то что сказать… значит вы не понимаете как работает это устройство 🙂

На самом деле, коэффициент усиления, или передачи не играет здесь никакой роли. Вспоминаем, в каких случаях это происходит? А это происходит тогда, когда система (громкое название для нашей схемки) охвачена сильной отрицательной обратной связью, и поэтому ее параметры определяются уже параметрами обратной связи, и в меньшей степени — параметрами самой системы. Найдем здесь эту отрицательную обратную связь.

По Дерибасовской гуляют постепенно

Рассмотрим процесс как в замедленной съемке, например после подачи питания +12В. При этом предположим, что транзистор отрабатывает медленно — настолько медленно, чтобы мы могли провести свой мысленный эксперимент.

После включения, с делителя напряжения R1/R2 потенциал через резистор R3 подается на базу транзистора. Транзистор начинает открываться (мы договорились о замедленной съемке), и по мере его открывания ток, протекающий от эмиттера к коллектору начинает увеличиваться. Увеличивается ток — значит возрастает падение напряжения на резисторе R5, или другими словами на эмиттере транзистора. Поскольку транзистору интересна разность потенциалов между базой и эмиттером (на самом деле ему больше интересен протекающий ток, но не будем мелочиться), то увеличение напряжения на R5 приводит к уменьшению этой разницы. Уменьшение — это уже процесс запирания транзистора. Вот это и есть отрицательная обратная связь.

В конечном счете, в системе установится равновесное состояние. Все, замедленное кино закончилось.

Равновесие

В этом состоянии напряжение эмиттера всегда будет повторять напряжение базы — поэтому по отношению к сигналу на резисторе R5 схема будет себя вести как эмиттерный повторитель. Здесь будет уместна аналогия с системами автоматического управления, когда сигнал обратной связи вычитается из входного и возникает сигнал рассогласования, или ошибки. В нашем случае, на самом деле сигнал на эмиттере будет меньше базового на 0,6В — таково падение напряжение на переходе кремниевого транзистора.

Теперь у нас есть все, что нужно для расчета, а именно понятый принцип работы.

Напряжение на выходе делителя R1/R2 = 12В x 18к/ (33к + 18к)  = 4,2В. Предполагаем, что в режиме эмиттерного повторителя ток в базовой цепи мал, поэтому это напряжение полностью прикладывается к базе. Тогда на эмиттере транзистор будет поддерживать напряжение 4,2В — 0,6В = 3,6В. Напряжение будет стабильным даже тогда, когда наша схема будет испытывать температурные перепады: не забываем, при прочих условиях при увеличении температуры среды на 10° ток коллектора будет удваиваться! Поэтому простые решения в аналоговой технике работают у любителей и совершенно непригодны в профессиональной области 🙂

Сразу сделаем еще один вывод: решения, зависящие от коэффициента передачи транзистора, не термостабильны.

Но мы отвлеклись. Дальше — дело техники. Поскольку напряжение на R5=3,6В то ток в эмиттерной цепи = 3,6В / 1k = 3,6мА. Такой же ток течет в коллекторной цепи: ведь мы же пренебрегаем малым током базы, не правда ли? Чуть позже выясним, так ли это.

В коллекторной цепи ток 3,6мА создает падение напряжения на резисторе R4. Оно будет равно 3,6мА х 1,8к ≈ 6,5 В. Тогда напряжение Uout составит 12В — 6,5В = 5,5В. Задачка решена.

Самопроверка

Теперь когда мы знаем токовые соотношения, проверим, насколько корректны допущения которые мы сделали. Если коэффициент передачи транзистора по току большой, как я сказал вначале, пусть он будет равен 100 (поскольку диссертации никто не читает, примем h=100). Тогда ток базы составит 36мкА. При таком токе падение напряжения на резисторе R3 составит 36мкА х 12к = 0.4В. Это очень мало по сравнению с тем напряжением, который держит делитель R1/R2: поэтому мы сделали правильно, что пренебрегли резистором R3 при расчете.

Далее, входное сопротивление цепи базы будет 4,2В / 36мкА = 117кОм. Это значение на порядок больше, чем сопротивления в плечах делителя напряжения R1/R2, поэтому делитель практически не нагружен и его выходное напряжение соответствует действительности.

Зачем тогда вообще нужен резистор R3, если мы пренебрегаем им сплошь и рядом? Несмотря на то что в цепи базы входное сопротивление — высокое, оно все равно шунтируется относительно низкоомным делителем R1/R2. Эта величина соответствует параллельному включению этих резисторов (поскольку для переменного входного сигнала цепь питания и «земля» это одно и то же — можно считать, что по переменному току они замкнуты). Входное сопротивление каскада составит 11,6кОм, и чтобы сделать его побольше, стоит резистор R3. С ним для источника сигнала нагрузка составит 11,6+12 = 23,6кОм, что уже неплохо. Повторюсь еще раз: входное сопротивление транзисторного каскада будет высоким — 117кОм, поэтому значение входного сопротивления всего каскада будет определять резистивная цепь.

AC/DC

Все наши рассуждения были справедливы как для постоянного тока (установка рабочей точки), так и для переменного (для усиления которого собственно и предназначена схема). Однако, есть нюанс. За счет отрицательной обратной связи усиление сигнала будет подавляться точно также, как и для постоянного тока. И точно также значение коэффициента транзистора будет играть второстепенную роль. Коэффициент передачи будет соответствовать соотношению номиналов резисторов R4 и R5 и будет составлять довольно скромную величину 1.8. Для того чтобы избавиться от обратной связи для сигнала, предназначен конденсатор C2. Для переменного напряжения он закорачивает резистор R5, что резко повышает коэффициент усиления всей схемы. Однако, не все так просто — после этого немедленно и кратно упадет входное сопротивление, хотя термостабильность останется. В результате возникнут проблемы для предыдущего каскада — у него упадет коэффициент усиления за счет дополнительной нагрузки.

Но кто обещал, что будет легко? Аналоговая схемотехника — это один сплошной компромисс. Компромиссным решением может стать дополнительный резистор, включенный последовательно с конденсатором C2. Это снизит эффект усиления и соответственно падения входного импеданса.

Роль конденсатора C1 в схеме тривиальна: развязка от предыдущих цепей по постоянному току.

Вот и все. За скобками остался анализ максимального тока коллектора, мощности, паразитных емкостей и частотной характеристики схемы. А так — все будет прекрасно работать.

FFT-on-Chip: Cross — ambiguity function в реальном времени на GPU

В статье про кросс-компиляцию я рассказал о том, как подготовить удобный инструментарий для работы с Raspberry Pi. Напомню, что статья началась с новости о том, что Broadcom открыл спецификации своего чипа GPU, который используется в RPi, что открыло возможности по быстродействующим вычислениям преобразования Фурье: БПФ/FFT на этом чипе.

Поскольку бродкомовские библиотеки у меня поднялись сразу, я не стал торопиться и подготовил пару питоновских утилит для моделирования входной выборки и визуализации выходных данных (спектр выборки). Дальше — больше: чтобы наработанный материал не пропадал зря, я сразу решил приспособить fft-on-chip технологию для нахождения кросс — функции неопределенности, которая используется в пассивной локации (PCL). В итоге, у меня получилось три приложения.

Три источника и три составные части FFT-on-Chip

Первое приложение — питоновская программа для формирования входной I/Q выборки. Для того чтобы обеспечить последующую визуализацию результатов работы, данные формируются блоками по принципу один блок — одна картинка. В результате все записывается в бинарный файл, который отдается приложению на RPi.

Для какого сигнала будем определять кросс — функцию неопределенности? Вначале я планировал сделать выборку близкой к реальному речевому/музыкальному сигналу, который транслируется ФМ станциями, что и нужно пассивному радару. Однако я обнаружил что закапываюсь в звуковых и ALSA модулях Питона и трачу много времени на то, чтобы распатронить mp3 запись с песней Тото Кутуньо в PCM формат, который уже можно преобразовать в I/Q последовательность. Поэтому я поступил просто: чтобы визуализация/анимация была наглядной, выбрал в качестве входного сигнала выборку М-последовательности, которые славятся хорошими автокорреляционными свойствами.

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

Мы пойдем простым путем. Помните, что каждый раз когда надо сделать просто, на помощь приходит Питон? Одна строчка и последовательность у нас в кармане, то есть в переменной m_seq:

Девятка — это длина последовательности как степень двойки. Дальше, самое время вспомнить что мы собираемся генерировать «кросс» функцию неопределенности, поэтому полученную выборку будем интерпретировать как опорную для пассивного радиолокатора, то есть полученную с базовой ФМ станции. Сам сигнал, отраженный от цели, должен получить доплеровский сдвиг по частоте (движение цели) и сдвиг по времени (задержка при отражении от цели). Опять таки, для наглядности будущей анимации сделаем эти параметры линейно меняющимися во времени. Сигнал и опору записываем в файл, и на этом генерация данных завершена.

Второе приложение на RPi: программа обработки данных и нахождения кросс — функции неопределенности. Здесь мы вовсю используем наработанный инструментарий. Приложение работает на ARM процессоре RPi и для вычисления FFT использует GPU модуль. Вне зависимости от того, какой из методов нахождения кросс — функции неопределенности мы используем, для входной выборки нужно выполнить серию FFT преобразований. И было бы обидно, если быстродействующую функцию БПФ нужно было вызывать каждый раз, теряя драгоценное время на вызов.

К счастью, разработчики спецификаций и библиотек дали возможность отправлять на разработку целый пакет выборок, возвращая пакет спектров БПФ. Пакетную обработку выполняет функция API gpu_fft_execute(fft). В результате, пакет комплексных переменных записывается в файл уже для последующей анимации.

С третьим приложением все просто. Питоновская программа получает файл с 2D блоками кросс — функций неопределенности и прокручивает его на экране. Поскольку в качестве входной выборки я задавал М — последовательности, хорошо видно пик диаграммы.

Естественно, пик перемещается, потому как мы задавали изменение доплеровской скорости и задержки во входных данных. Для наглядности я крутил функцию неопределенности в разные стороны, чтобы были видны ее сечения как по времени, так и по частоте.

Coming Soon

В основном приложении я не упомянул про важный модуль, который обеспечивает подавление опорного сигнала во входных данных. Этот метод основан на сложной математической процедуре и реализован адаптивным способом. Об этом я расскажу в другой статье; надеюсь к этому моменту можно будет использовать вместо М — последовательностей аудио — данные.

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

АЗН-В/ADS-B: изделие — система — сервис

«Два мира — два Шапиро» (популярная цитата советских времен)

Рассказывая про поездку в американскую компанию ITT Exelis, отложил на потом самую суть: как устроена федеральная сеть ADS-B, которую разрабатывала эта компания. Это именно сеть, поскольку осмысливая результаты этого визита, стало ясно, что на западном рынке никто уже не работает на уровне абстракций изделия:

Читать дальше

Термопринтер Zebra: печать из МоегоСклада под Ubuntu/Linux

Пришло очередное время пополнения инструментария. В хозяйстве появился принтер этикеток Zebra ZD410 — как оказалось вещь крайне нужная, потому что печатать таблицы на клейкой бумаге — это сущий ад. В онлайн — сервисе «МойСклад», который мы используем как облегченную версию 1С, есть функционал печати термоэтикетки для каждого товара из справочника. Вначале я не обращал на

Читать дальше

Нейронный автокодер / Neural Autoencoder: отбрасывая лишнее

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

Читать дальше

Офшорная радиолокация

В разработке отечественных радиоэлектронных систем вплоть до 90-х годов было принято вести разработку всех компонентов самостоятельно. Антенна, мачта, источники питания — под каждое направление на предприятии были соответствующие секторы и отделы. С ростом сложности изделий одновременно росла роль специализации. Появились небольшие компании, которые фокусировались на высокотехнологичных компонентах: малошумящие СВЧ усилители, процессорные модули, модули АЦП/ЦАП вплоть

Читать дальше

Эффект полостных структур Гребенникова

Виктор Степанович Гребенников прожил трудную жизнь. Среди ученых он известен как фанатично преданный своему делу энтомолог. Любил своих подопечных — насекомых настолько, что создал в окрестностях Новосибирска, где жил и работал, заповедники (заказники) для насекомых.

Заповедник для насекомых! Просто нет слов.

Фотография платформы Гребенникова из книги «Мой Мир»

Будучи талантливым художником, он постоянно рисовал

Читать дальше

Псевдокогерентная РЛС / Coherent-on-receive: обработка сигнала

Радиолокатор П-10

Поскольку освоение радиочастотных диапазонов начиналось от длинных волн к коротким, первые радиолокационные станции — РЛС прошли эволюцию от метровых диапазонов к все более и более высоким частотам. Преимущества очевидны: существенное сокращение размера антенных систем, которые обречены соответствовать длине волны, снижение излучаемой мощности, а также сокращение объема оборудования. С появлением твердотельных передатчиков, зависимых

Читать дальше

Кросс — функция неопределенности: два способа получения

В применении к задачам пассивной радиолокации, в конечном счете двумерное изображение радиолокационной обстановки формируется с помощью кросс — функции неопределенности (ФН):

(1)

Приставка «кросс» означает, что в отличие от классической ФН одного сигнала, выражение содержит взаимную функцию неопределенности сигнала s(Δt, Δf), переотраженного от цели с приобретенной задержкой Δt и доплеровским сдвигом частоты

Читать дальше