Hardware engineering and etc.

Variable frequency scalar control for 3-Phase AC induction motor -- STM32 implementation

2011-12-30T14:51:00.000-08:00

Это часть проекта по созданию частотного преобразователя для асинхронных двигателей средней мощности.
В качестве аппаратной платформы был выбран микроконтроллер STM32, в силу его дешевизны и доступности специальных библиотек (STM32_FOC_ACIM из stm32 foc firwmare libraries v2.0).
Здесь описано самое начало работы: запуск маленького асинхронного двигателя в скалярном режиме (V/f-управление).

В результате беглого просмотра исходников STM32_FOC_ACIM выяснилось, что скалярный режим там не предусмотрен, а нам он был важен для проверки трехфазного IGBT-моста и вообще оживления двигателя без датчиков обратной связи.

Был создан новый проект, из библиотеки STM32_FOC_ACIM взята только таблица синусов и функции работы с таймером (SVPWM -- векторная модуляция). Приделан DDS для генерации синусоидальных сигналов управления SVPWM-модулятором с плавной перестройкой частоты.

В результате получилось то, что представлено на картинке:

платка STM32VLDISCOVERY подключена к модулю трехфазного IGBT-моста, от которого запитан совеццкий мини-асинхронник (первый попавшийся, вообще-то с фазным ротором, но фазная обмотка была замкнута). Крутилка, подключенная ко входу АЦП микроконтроллера, задает скорость -- можно плавно менять от 0 Гц до 50 Гц.

Вот напряжения на двух фазах

Сейчас добавляется новый функционал и все это тестируется на более реальных двигателях.

Скачать исходный код проекта

Remote serial COM-port implementation on STM32

2011-08-20T05:44:00.000-07:00

Собственно история такая: срочно для одного проекта необходимо было сделать удаленный COM-порт.

Это должно было выглядеть так: на компьютере устанавливается виртуальный COM-порт, данные из него пересылаются по TCP/IP на удаленное устройство, собранное на микроконтроллере STM32F107 (connectivity line), где они выдаются наружу через UART. Тоже самое, но только в обратном направлении для данных, приходящих на UART микроконтроллера.

Я рассматривал для варианта реализации на библиотеке uIP и библиотеке lwIP. Оба варианта без операционной системы. До этого не приходилось тесно работать с этими библиотеками, а выбор был сделан, поскольку они портированы на STM32 и исходники доступны.

На компьютере был установлен драйвер com0com для создания пары связанных виртуальных COM-портов. Также использовалась программа com2tcp которая собственно занималась передачей данных из виртуального порта через сокеты TCP/IP. Цепочка передачи выглядела таким образом:

com2tcp запускалась из командной строки с параметрами
com2tcp --ignore-dsr \\.\CNCB0 192.168.0.8 23

С uIP ничего хорошего не получилось -- потому что при отсылке пакетов из STM32 постоянно срабатывал тайм-аут и происходило рассоединение. Вероятно, причина в неправильной настройке таймера, но я глубже не разбирался и решил попробовать что-то другое.
Скачанный с st.com порт lwIP работал устойчиво, добавляем пару строк для работы с UART в исходниках реализации telnet, тестим -- и девайс готов :)

В качестве аппаратной платформы использовалась отладочная плата STM3210C (EM-STM3210C).

Исходники для STM32

Pseudo-Arclength numerical continuation method -- quick & dirty MATLAB code

2011-07-08T08:54:00.000-07:00

Я уже как-то писал про методы продолжения по параметру (homotopy numerical continuation). Весьма полезная штука для решения систем нелинейных уравнений. Мне нужна была программка для эксперементирования с некоторыми своими идеями и буквально за 20 минут набросал код в MATLAB, который реализует один из вариантов метода гомотопического продолжения по параметру, а именно "pseudo-arclength method". Никакой оптимизации кода не проводилось, некоторые вещи можно было бы сделать проще и быстрее (в частности, там кое-где постоянно вычисляется детерминант, хотя он согласно свойству QR-разложения, всегда равен 1), особо не тестировалось -- короче это "quick & dirty" код.

Рассматривается кривая $x = \phi(\lambda)$ заданная неявно в виде $H(x,\lambda) = 0$ на интервале $\lambda \in [0, 1]$:

$$H(x,\lambda) = (1-\lambda) \cdot (x - x_0) + \lambda \cdot f(x)$$

где $f(x)$ -- система нелинейных уравнений (квадратная), корень которой необходимо найти (задается в файле fun.m, ее якобиан -- в dfun.m); $x_0$ -- начальное приближение.

Плавно изменяя параметр $\lambda$ от 0, где очевидно $H(x_0, 0) = 0$ до $\lambda = 1$, постоянно при этом находя $x$, обращающий в 0 $H$, мы получаем в результате решение исходного уравнения $f(x) = 0$. Так реализуется идея постепенного плавного перехода от очень простой задачи $x - x_0 = 0$ к исходной $f(x) = 0$.

Смысл реализованного метода в следующем.

1. Сначала в точке $(x,\lambda)$, где $H(x,\lambda) = 0$, определяется тангенциальный вектор $t = (x',\lambda')$ единичной длины и положительной ориентации. Это просто делается QR-разложением якобиана отображения $f(x)$.

2. Потом реализуется шаг предиктора: точка $(x,\lambda)$ сдвигается на небольшое расстояние $\Delta t$ в направлении $t$. Шаг предиктора продвигает решение в верном направлении к решению $f(x) = 0$, но в резальтате мы оказываеся не на кривой $H$.

3. Далее реализуется шаг корректора: точка $(\bar x, \bar \lambda)$, полученная после шага предиктора перемещается таким образом, чтобы оказаться на кривой $H(x,\lambda) = 0$. Это реализуется с помощью метода Ньютона, применяемого к композитной функции: $F(x, \lambda) = (H, N)^T(x, \lambda)$:

$$\begin{pmatrix} \dot x \\ \dot \lambda \end{pmatrix} = - \begin{pmatrix} D_x H & D_\lambda H \\ D_x N^T & D_\lambda N \end{pmatrix}^{-1} \begin{pmatrix} H \\ N \end{pmatrix}$$

где $$N(x, \lambda) = (x')^T(x - \bar x) + \lambda'(\lambda - \bar \lambda) - \Delta t = 0$$ -- нормаль к кривой $H$, проходящая через точку $(\bar x, \bar \lambda)$.

Собственно исходник -- pseudo_arclength_test.rar

Filament Display

2011-04-20T13:01:00.000-07:00

Сегодня я видел удивительную вещь, которую вряд ли еще увижу. Это называется накальный вакуумный индикатор или filament display. Т.е. это такой семисегментный индикатор, у которого каждый сегмент -- это лампочка накаливания.

Вот фотки (извиняюсь за качество, фоткал на мобильный).

Также еще хочу сказать, что в детстве, когда я делал электронные часы на микросхемах К155 (гыгы), то мне почему-то очень хотелось заполучить такие индикаторы (не могу вспомнить почему), и из справочника я точно знал, что такие бывают. Но их никто никогда не видел. А оказываются-таки да, существуют))

Numerical homotopy continuation

2011-04-20T12:44:00.001-07:00

Вся теория и книжки могут быть сжаты в одно предложение: если у нас есть отображение $H: \mathbb{R}^{n+1} \to \mathbb{R}^{n}$, то это означает, что уравнение $H = 0$ задает неявную функцию $f: \mathbb{R} \to \mathbb{R}^{n}$, которую мы можем численно аппроксимировать, если знаем хотя бы ее одну точку $(t_0, f(t_0))$

По-русски, это называется метод продолжения по параметру. Сама функция $f(t)$ может вести себя не слишком хорошо: пересекаться с какой-то другой кривой, тоже заданной неявно из $H$, или быть неинъективной. Но это не очень страшно.

STM32 discovery IAR project from st.com

2011-04-19T11:27:00.000-07:00

Внезапно узнал, что demo-проект для STM32 discovery (AN3268) не собирается в IAR. Вылазит куча сообщений типа:
"could not open source file "STM32f10x.h""
"identifier "GPIO_Pin_9" is undefined"
и т.д.
Все ок, просто они почему-то выкладывают проект, в котором не проиписаны пути к .h
файлам и define-ы. Кроме того, там еще не указаны границы памяти микроконтроллера...

Вот исправленный файл проекта (только сам проект для IAR), без исходников.

Там надо было просто в настройках С++ Compiler/Preprocessor/Additional include directories прописать такое (PROJ_DIR -- с двух сторон знак доллара):
PROJ_DIR\..\..\..\Libraries\CMSIS\CM3\CoreSupport
PROJ_DIR\..\..\..\Libraries\CMSIS\CM3\DeviceSupport\ST\STM32F10x
PROJ_DIR\..\..\..\Libraries\STM32F10x_StdPeriph_Driver\inc
PROJ_DIR\..\inc
И ниже в Defined Symbols:
STM32F10X_MD_VL
USE_STDPERIPH_DRIVER

Почему выкладываются нерабочие демо-проекты -- не знаю, может быть чтобы юзеры ковырялись в исходниках))

Linear Control of Nonlinear Systems - I

2010-08-02T13:21:00.000-07:00

Вообще в системах управления, как в теории, так и на практике, меня очень привлекает один момент. Когда вокруг некоторого объекта управления мы замыкаем обратную связь, то возникает самое настоящее волшебство:
- мы можем сделать из нелинейного объекта управления линейный, причем сделать это можно с помощью линейной обратной связи (т.е. простых ПИД-регуляторов),
- мы можем сделать из нескольких объектов (или одного, но изменяющегося во времени) какой-то один заданный, который будет вести себя почти одинаково (свойство робастности).

Философски, это означает, что мы можем относительно простыми средствами существенно изменить какой-то объект, обладая только ограниченным пониманием его работы.

Тривиальный иллюстративный пример: возьмем систему вида

$$\dot{x} = u - x$$
$$y = x^3 - x$$

Нетрудно видеть, что она состоит из лаговой задержки первого порядка и кубического нелинейного элемента. Если пытаться произвести точную линеаризацию такой системы (exact feedback linearization), то возникают трудности с нерегулярностью трансформирующего преобразования. Мы имеем систему после дифференцирования вида $\dot{y} = (3x^2 - 1)(u - x)$ и в точках $x = \pm \sqrt{3^{-1}}$ возникает потеря управляемости.

Но если взять обычный пропорционально-интегральный регулятор, то никаких проблем с управлением нет.

Для более подробного анализа рассмотрим принципы робастного управления линейными системами. На самом деле, нет ничего проще, чем линейное робастное управение))

Робастное управление рассматривает систему с замкнутой обратной связью $\Sigma: U \to Y$ как суперпозицию систем $\Sigma=(M,\Delta)$, где $M: U \times D_o \to Y \times D_i$ -- номинальную систему, $\Delta: D_i \to D_o$ -- объект, моделирующий неопределенность. Все дальнейшее рассуждение подразумевает, что $M$ устойчиво в отсутсвии неопределенности при $\Delta = 0$.

Номинальный объект $M$ рассматривается как четырехполюсник, отсюда можно записать уравнение:

$$\begin{pmatrix} d_i \cr y \end{pmatrix} = \begin{pmatrix} M_{11} && M_{12} \cr M_{21} && M_{22} \end{pmatrix} \begin{pmatrix} d_o \cr u \end{pmatrix}$$

Для того, чтобы установить необходимое и достаточное условие робастной устойчивости, рассмотрим действие операторов на сигналы. Поскольку

$$d_i = M_{11} \cdot d_0 + M_{12} \cdot u$$

то верно неравенство треугольника

$$\|d_i\| \le \|M_{11}\| \cdot \|d_0\| + \|M_{12}\| \cdot \|u\|$$

где нормы операторов и сигналов понимаются в привычном смысле (по Лебегу).

Аналогично для оператора $\Delta$ и выхода

$$\|d_o\| \le \|\Delta\| \cdot \|d_i\|$$
$$\|y\| \le \|M_{21}\| \cdot \|d_o\| + \|M_{22}\| \cdot \|u\|$$

Заменив неравенства на равенства и подставив в последнее выражение, находим оценку для выхода $\|y\| \le \phi(M,\Delta) \cdot \|u\|$:

$$ \phi(M,\Delta) = \frac{\|\Delta\| \cdot \|M_{21}\| \cdot \|M_{12}\|}{1-\|\Delta\| \cdot \|M_{11}\|} + \|M_{22}\| $$

Отсюда необходимым и достаточным условием робастной устойчивости системы в присутсвии неопределеннсоти $\Delta$ является выполнение неравенства:

$$ \|\Delta\| \cdot \|M_{11}\| < 1 $$

Теперь перейдем к нелинейным системам.

Простейшее усовершенствование рассмотренной модели состоит в том, чтобы сделать оператор $\Delta$ -- нелинейным. Условие устойчивости, приведенное выше в этом случае очевидно сохраняется.

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

$$ \Sigma = (\Delta + G) \circ Q $$

где $\Delta$ -- нелинейная часть, $G$ -- линейная система, $Q$ -- сатуратор, ограничивающий входные воздействия по амплитуде.

Пусть $C$ -- контроллер, работающий по сигналу ошибки $C: U \times Y \to V$, $C: u - y \mapsto v$, и подключенный ко входу системы $\Sigma : v \mapsto y$.

На самом деле, замкнутая система $(\Sigma, C)$ и рассмотренная выше $(M, \Delta)$ -- эквиваленты. Поскольку нелинейность в $\Sigma$ действует аддитивно, то ее можно всегда изолировать и в таком случае номинальная система окажется остатком $M = (\Sigma, C) / \Delta$.

Можно показать, что система $(\Sigma, C) / \Delta$ представима в виде четырехполюсника, в котором

$$M_{11} = C (I + G Q C)^{-1}$$

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

- представление нелинейной системы в виде суперпозиции $ \Sigma = (\Delta + G) \circ Q $,

- вычисление нормы $\|\Delta\|$ нелинейного компонента с учетом вносимых $Q$ ограничений,

- синтез линейного контроллера $C$, который бы удовлетворял неравенству $\|C (I + G Q C)^{-1}\| < {\|\Delta\|}^{-1}$.

W/ wires

2010-06-30T15:28:00.000-07:00

Просто красивая плата, недавнее творение рук своих, так сказать))

На самом деле, ничто иное как многоканальный сервоконтроллер DC-двигателей. Внутри -- ПИД на 10 каналов для позиционирования, Ethernet и другие примочки.

A bit of a systematic approach to the decimation filters for sigma-delta ADC

2010-05-14T15:10:00.000-07:00

1. Сигма-дельта АЦП

Всем известно, что сигма-дельта АЦП -- это очень здорово. Мне нравится такой тип АЦП потому что он наиболее полно реализует подход перенесения функционала в информационное (аппаратное/программное) обеспечение. Относительно простой аналоговый front-end вместе с последующей цифровой обработкой дают отличные параметры и стоимость.

Большинство микросхем сигма-дельта АЦП -- интегрированное решение, пользователь которого может даже и не знать как это работает внутри: снаружи виден только код. Но настающую гибкость можно получить, используя чистый сигма-дельта модулятор (например, от Analog Devices типа AD7400/AD7401 или AD7724) с реализацией фильтра на FPGA или DSP. Кстати, AD7400/AD7401 -- особенно полезны в силовой электронике потому что содержат внутри себя гальванический изолятор ADuM.

Удобство состоит в том, что двоичный поток с выхода модулятора может быть обработан параллельно несколькими фильтрами, в результате чего могут быть получены АЦП различных выходных характеристик. Например, медленное для точного измерения эффективного/амплитудного значения тока и быстрое для детектирования перегрузки по току.

Этот подход проиллюстрирован на рисунке ниже, где с выхода SINC3-фильтра поступают 16-и битные данные с задержкой примерно 60 мкс, а с FIR-фильтра -- 5-и битные с задержкой 4 мкс, что позволяет организовать вместе с измерениями быстродействующую защиту.

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

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

2. Эффективная разрядность

Пусть АЦП работает на частоте дискретизации $f_s$. Тогда спектральный шум квантования $E(f)$ определяется как:

$$ E^2(f) = \frac{\sigma^2}{f_s} = \frac{A^2}{12 f_s} 2^{-2n}$$

где $\sigma$ -- мощность шума квантования АЦП по амплитуде, $A$ -- максимальный измеряемый сигнал, $n$ -- число разрядов.

Для сигма-дельта АЦП, очевидно $n=1$, и $E^2(f) = A^2/(48 f_s)$.

Идея состоит в том, что, пропустив шум квантования через сигма-дельта модулятор и фильтр, можно получить некоторую спектральную характеристику $\hat E^2(f)$ и интегральную мощность шума $\hat \sigma$. По значению $\hat \sigma$ можно определить число эффективных разрядов выходного кода:

$$ n = -\frac{1}{2} \log_2 \left( 12 \frac{\hat \sigma^2}{A^2} \right) $$

Известно, что сигма-дельта модулятор порядка $m$ описывается в z-области выражением:

$$ H_m(z) = (1-z^{-1})^m $$

и его амплитудно-частотная характеристика:

$$ H_m(f) = 2^m \left| \sin \frac{\pi f}{f_s} \right|^m $$

Если $H(f)$ -- амплитудно-частотная характеристика децимирующего фильтра, то интегральную мощность шума на его выходе может быть определена как:

$$\hat \sigma^2 = \int_{-f_s/2}^{f_s/2} \left( H_m(f) H(f) E(f) \right)^2 df$$

или

$$\hat \sigma^2 = \frac{2^{2m} A^2}{48 f_s} \int_{-f_s/2}^{f_s/2} \left( \sin \frac{\pi f}{f_s} \right)^{2m} H^2(f) df$$

Отсюда эффективное число разрядов в общем виде:

$$ n = -\frac{1}{2} \log_2 \left( \frac{1}{f_s} \int_{-f_s/2}^{f_s/2} \left( \sin \frac{\pi f}{f_s} \right)^{2m} H^2(f) df \right) - m + 1 $$

Это соотношение очень полезно на практике -- оно позволяет по частотной характеристике децимирующего фильтра (или ее аппроксимации) сказать какая точность АЦП в результате получится.

3. Пример -- MATLAB

Рассмотрим следующий пример: необходимо обеспечить токовую защиту в цепи с катушкой индуктивности, которая быстро входит в глубокое насыщение при коротком замыкании. Параметры системы измерения:
- частота дискретизации однобитного сигма-дельта АЦП: $f_s = 12.5 \cdot 10^6 Hz$,
- порядок сигма-дельта модулятора: $m=2$,
- время реакции на превышение тока сверх предельного значения: $\tau \le 4 \cdot 10^{-6} s$,
- эффективная разрядность: $n \ge 5$.

Из требований по времени реакции $\tau$ следует, что частота среза децимирующего фильтра должна быть $f_p \ge \tau^{-1}$. Можно выбрать коэффициент децимации $k=32$ и $f_p = f_s/k$.

С помощью средства filterbuilder в MATLAB синтезируем FIR-фильтр порядка 32 с нормированной частотой среза $1/k$, и агрессивно квантизируем его реализацию: вход -- данные с фиксированной точкой 7+1 бит, длина коэффициентов -- 9 бит.

Численное интегрирование с помощью этого MATLAB-скрипта дает эффективную разрядность: $n = 6.2749$.

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

зеленая кривая -- импульс на входе сигма-дельта модулятора,
синяя кривая -- выход фильтра.

Из моделирования видно, что время реакции АЦП на импульсный сигнал составляет около 2 мкс.

4. Пример -- реальне железо

Рассмотрим результат испытания полученного выше фильтра. В качестве сигма-дельта модулятора использовалась микросхема AD7401, ток в цепи измерялся индуктивным датчиком с полосой пропускания 200 кГц.

Исходный код фильтра получен автоматической генерацией на язык Verilog из средства filterbuilder. Единственная модификация кода состояла в конвертировании битового потока с целые числа, поступающие на вход фильтра: значение 0 -- в -128, значение 1 -- в +127. После синтеза для Altera Cyclone III EP3C25E144C8N фильтр занимает 450 логических ячеек.

Для реализации функции защиты от короткого замыкания выход фильтра АЦП непрерывно сравнивается с эквивалентным значением тока 25 А и при превышении -- цепь разрывается.

Осциллограмма сигналов в схеме без защиты:

фиолетовый канал -- ток в цепи (использовался токовый делитель 1:20),
синий канал -- сигнал короткого замыкания в схеме,
желтый канал -- сигнал срабатывания защиты.

Видно, что за время менее чем 10 мкс после превышения значения 25 А ток в цепи вырос до более чем 80 А.

Осциллограмма сигналов в схеме с включенной защитой:

(сигналы те же, что и в схеме без защиты)

Видно, что схема защиты срабатывает спустя 2.5 мкс после превышения порогового значения (25 А) и ток в цепи не больше 44 А.

5. Файлы для скачивания

Функция для вычисления эффективной разрядности
Скрипт в MATLAB с рассмотренными примером
Verilog код фильтра и do-файл для моделирования в ModelSim

On algebra of systems - I

2010-03-14T15:55:00.000-07:00

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

Будем рассматривать абстрактные системы вида:

$$S : X \to Y$$

где $X,Y$ -- какие-то абстрактные объекты (например, множества), описывающие входные и выходные воздействия. Функциональную зависимость $S$ можно интерпретировать как отношение на произведении: $S \subseteq X \times Y$.

В отображаемых системой объектах выделим компоненты $X^*,Y^*$ участвующие в композиции, т.е. можно записать $S : (X \times X^*) \to (Y \times Y^*)$.

Последовательное соединение двух систем $S = S_1 \odot S_2$, где $S_1 : X_1 \to (Y_1 \times Y_1^*)$ и $S_2 : (X_2 \times X_2^*) \to Y_2$ -- это система $S : (X_1 \times X_2) \to (Y_1 \times Y_2)$, полученная подстановкой $X_2^* := Y_1^*$ в $S_2$. Более формально, $S (X_1 \times X_2) = \pi_{Y_1} \circ S_1(X_1) \times S_2(X_2 \times \pi_{Y_1^*} \circ S_1(X_1))$, где $\pi_{Y_1}, \pi_{Y_1^*}$ -- соответствующие канонические проекции.

Параллельное соединение двух систем $S = S_1 \oplus S_2$, где $S_1 : (X_1 \times X_1^*) \to Y_1$ и $S_2 : (X_2 \times X_2^*) \to Y_2$ -- это система $S : (X_1 \times X_2) \times X \to (Y_1 \times Y_2)$, полученная объединением входов: $X := X_1^* = X_2^*$. Более формально, $S (X_1 \times X_2 \times X) = S_1(X_1 \times X) \times S_2(X_2 \times X)$.

Замыкание обратной свзи $\hat{S}$ в системе $S : (X \times X^*) \to (Y \times Y^*)$ -- это система $\hat{S} : X \to Y$, полученная подстановкой $X_1^* := Y_1^*$ в $S$. Более формально, $\hat{S}(X) = S(X \times Z)$, где $Z = \pi_{Y^*} \circ S(X \times Z)$.

Операции $\odot, \oplus, \hat{}$ -- замкнуты по отношению к базовому множеству систем $\mathcal{S}$:

$$ \odot : \mathcal{S} \times \mathcal{S} \to \mathcal{S} $$
$$ \oplus : \mathcal{S} \times \mathcal{S} \to \mathcal{S} $$
$$ \hat{} : \mathcal{S} \to \mathcal{S} $$

Довольно очевидно, что операции композиции ассоциативны:

$$ (A \odot B) \odot C = A \odot (B \odot C) $$
$$ (A \oplus B) \oplus C = A \oplus (B \oplus C) $$

Ничто не мешает коммутативности параллельной композиции:

$$ A \oplus B = B \oplus A $$

Нейтральным элементом $0$ для операции параллельного соединения является пустая система: $0 : \varnothing \to \varnothing$, поскольку $S \oplus 0 = S$. По отношению к параллельной композиции инверсный элемент $\ominus S$ -- это такой, что нейтрализует действие системы $S \oplus \ominus S = S \ominus S = 0$.

Можно определить обратные элементы для операции последовательной композиции. Систему $S : X \to Y$ можно преобразовать в $1_X : X \to X$ и $1_Y : Y \to Y$ c помощью последовательного соединения с соответственно правой $S^{-1} : Y \to X$ и левой инверсией $^{-1}S : Y \to X$ :

$$ S \odot S^{-1} = 1_X $$
$$ {}^{-1}S \odot S = 1_Y $$

Далеко не у каждой системы $S \in \mathcal{S}$ существует обратный элемент по отношению к операции последовательной композиции. Если $X,Y$ -- множества, то $S$ инвертируема тогда и только тогда, когда $S$ -- автоморфизм, т.е. $X=Y$. Далее будем рассматривать инвертируемые системы.

Операция последовательной композиции не коммутативна:

$$ A \odot B \ne B \odot A $$

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

$$ A \odot (B \oplus C) = (A \odot B) \oplus (A \odot C) $$

но правый дистрибутивный закон не выполняется.

Также верно правое дистрибутивное свойство сложения:

$$ (A \odot B) \oplus C = (A \oplus C) \cdot (B \oplus C) $$

но левый дистрибутивный закон не выполняется.

Таким образом, $(\mathcal{S}, \oplus)$ -- коммутативная группа, $(\mathcal{S}, \odot)$ -- некоммутативная группа, обе структуры объединены с помощью левого дистрибутивного свойства умножения и правого для сложения.

Алгебраическую структуру $(\mathcal{S}, \odot, \oplus)$ можно классифицировать двойственно. По отношению к дистрибутивности сложения эта структура -- почти-кольцо (nearring), в которой мультипликативная структура дополнительно обладает свойствами коммутативности и существования нейтрального элемента. По отношению к дистрибутивности умножения эта структура -- также почти-кольцо (nearring), в которой мультипликативная структура содержит нейтральный элемент и инверсию, а аддитивная -- обладает свойством коммутативности и также содержит нейтральный элемент.

Интересно, что конструкции типа seminearring очень сильно связаны с алгеброй процессов (Process Algebra).

Про обратную связь -- в следующий раз :)

On simple switching feedback linearization control

2010-02-20T14:54:00.000-08:00

В прошлый раз я сказал, что все равно: решать систему уравнений или управлять динамической системой -- в какой-то степени это подобные вещи ;-)

Вернемся к динамической системе $\Sigma$:

$$\dot{X} = U - X$$
$$Y = Y(X)$$

Что если $\det J_Y = 0$? Тогда обычная линеаризация не работает.

Пусть $N_{\epsilon}(X^@) = \{X \in \mathbb{R}^n | X = X^@ + \delta, \det J_Y(X^@) = 0, |\delta| < \epsilon\}$ -- окрестность вокруг точки сингулярности якобиана.

В области $N_{\epsilon}(X^@)$ мы в самом деле имеем систему, отличную от $\Sigma$. В этой области полной линеаризации системы $\Delta = \mu(\Sigma)$ не существует.

Я предлагаю сделать следующее: воспользоваться тем, что траектория $X(t)$ -- непрерывна. Это означает, что

$$X(t + dt) = X(t) + \dot{X} dt + o(\| dt \|) \approx X(t) + (U(t) - X(t)) dt$$

т.е. мы можем продлить фазовую траекторию через $N_{\epsilon}(X^@)$, аппроксимировав ее прямой линией.

Дискретизировав про времени, получаем следующее: если в какой-то момент времени $t=t_d$ оказывается, что $\det J_Y(X^{t_d}) \approx \epsilon$, то имеет смысл "заморозить" вычисление инверсии якобиана, сохранив прежнее $C = J_Y^{-1}(X^{t_d}) (Y^{t_d} - Y^*)$ и итерируя далее по прямой:

$$X^{t+1} = X^{t} - C \cdot \delta t$$

до тех пор пока не станет снова $\det J_Y(X^{t}) > \epsilon$.

С другой стороны, в некоторых случаях непрерывной траектории $X(t)$, проходящей через $N_{\epsilon}$, не существует. Можно показать, что если

$$ \operatorname{sign} \det J_Y(X(t_d)) \ne \operatorname{sign} \det J_Y(X(t_d) + \dot{X}_{t=t^d} dt) $$

то никакое управление $U(t), t \in [t_d, \infty)$ не продлит траекторию через область сингулярности $N_{\epsilon}$.

В этим примере нетривиально то, что мы получаем гетерогенную систему с двумя дискретными состояниями $S = \{ S_f, S_a \}$: $S_f$ -- состояние полной линеаризуемости системы и $S_a$ -- состояние приближенной линеаризации с замещением $\Sigma$ линейной моделью. И соответственно теория гетерогенных систем может быть использована для поиска ответов на такие вопросы:
- всегда ли такой итеративный процесс сойдется к конечному состоянию (решению),
- возможна ли другая стратегия управления в области сингулярности?
и т.д.

Newton method from a control theoretic point of view

2010-02-20T12:59:00.000-08:00

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

Пусть необходимо решить систему уравнений вида $Y(X)=Y^*$, которая все равно что $\hat Y(X)=Y(X)-Y_0=0$.

Классический метод Ньютона (Newton's method) состоит том, что если $J_{Y}$ -- якобиан $Y(X)$, то итерируя по формуле с какого-то $X^{0}$:

$$X^{t+1} = X^{t+1} - J_{Y}^{-1}(X^t) \cdot (Y(X^t)-Y^*)$$

в конце мы получим искомый $Y(X^*) = Y^*$.

Как на это можно посмотреть с позиций теории управления?

В терминах управления, решить исходную систему -- значит перевести объект из какого-то исходного состояния $X^{0}$ в состояние решения $X^*$ где $Y^*=Y(X^*)$.

Свяжем с решаемым уравнением следующую динамическую систему $\Sigma$:

$$\dot{X} = U - X$$
$$Y = Y(X)$$

где $U \in \mathbb{R}^n$ -- входные воздействия, $X \in \mathbb{R}^n$ -- пространство состояний.

Очевидно, эта динамическая система -- просто исходное уравнение, на вход которого подаются переменные, пропущенные через элемент задержки (лаг первого порядка).

Поскольку речь идет про нелинейное управление, то осуществим полную линеаризацию (feedback linearization) системы $\Sigma$ -- т.е. сделав так, чтобы данная система "выглядела" снаружи как некоторая линейная система $\Delta$. Иными словами у нас есть морфизм $\mu$, отображающий системы управления:

$$ \mu : \Sigma \to \Delta $$

Проделав то, что предлагает метод полной линеаризации систем управления, получаем следующую систему $\Delta$:

$$ \dot{Y} = V $$

которая получается из исходной $\Sigma$ подстановкой $U = J_Y^{-1} V + X$.

С помощью преобразования $\mu$ мы свели задачу управления нелинейной системой к задаче управления линейной. Как известно, система $\Delta$ может быть стабилизирована статической отрицательной обратной связью: положив $V = k \cdot (Y^* - Y)$, где $k$ -- коэффициент обратной связи и $Y^*$ -- правая часть уравнения как референсная точка. После переходного процесса в управляемой системе, получаем на выходе $Y^*$ и в пространстве состояний искомое решение $X^*$.

Дискретизируем все это по времени с шагом $\delta t$. Получаем итерации в системе $\Delta$:

$$V^{t+1} = k\cdot(Y^* - Y^t)$$
$$Y^{t+1} = Y^t + V^{t+1} \delta t$$

И в исходной системе $\Sigma$:

$$V^{t+1} = k\cdot(Y^* - Y^t)$$
$$U^{t+1} = J_Y^{-1}(X^t) V^{t+1} + X^t$$
$$X^{t+1} = X^{t} + (U^{t+1} - X^t) \delta t$$

что после подстановки дает

$$X^{t+1} = X^{t} - J_Y^{-1}(X^t) \cdot (Y^t - Y^*) (k \cdot \delta t)$$

Если сказать, что $(\delta t)^{-1} = k$ -- коэффициент обратной связи в стабилизаторе, то полученное выражение полностью совпадает с итерацией в методе Ньютона :)

DSP-based control : Hands-On example

2010-02-13T11:14:00.000-08:00

Снова простой пример из практики дает повод к глубоким размышлениям.

1. Позиционирование.

Вернемся к задаче позиционирования. Речь идет об управлении системой с интегратором вида $P(s)=k/s$. Как можно решить эту задачу, применяя подход цифровой обработки сигналов? :-)

Объект управления $P$, в самом деле, не более чем цифровой фильтр. Значит, необходимо синтезировать комплементарный ему цифровой фильтр $C(z)$ так, чтобы их композиция $P(z) \cdot C(z)=S(z)$ удовлетворяла некоторой спецификации $S(z)$.

Очевидно, что разомкнутая система с интегратором неустойчива и последовательным соединением с фильтром не может быть стабилизирована. В таком случае, перед синтезом фильтра необходимо охватить $P$ обратной связью. Получим из $P(s)=k/s$ нечто вроде $P(s)=k/(s+\lambda)$. Легко проверить, что отрицательная обратная связь с коэффициентом усиления $\lambda/k$ дает искомый результат.

Перейдя в дискретную область, получаем

$$P(s)=k/(s+\lambda) \mapsto P(z)=\alpha z^{-1}/(1-\beta z^{-1})$$,

где $\alpha = \frac{2 k T}{2+T \lambda}, \beta = \frac{2-T \lambda}{2+T \lambda}$.

Идеальный вариант, если будет $S=1$, тогда $C(z)=P^{-1}(z)$. Но в данном случае такой контроллер не может быть реализован, поскольку не является каузальным:

$$C(z)=\alpha^{-1}z/(1-z^{-1} \beta)$$

Для реализации фильтра $C(z)$ можно применить подход Шеннона-Боде, который заключается в том (если грубо), что исходный фильтр представляется как суперпозиция $C(z)=H_w(z)H^{*}(z)$ стабильного и минимально-фазового выбеливающего фильтра $H_w(z)$ и фильтра $H^{*}(z)$ -- каузальной аппроксимации $H(z) = C(z)H^{-1}_w(z)$, полученной удалением всех некаузальных составляющих из импульсной характеристики.

Получим $H_w(z)$, вычислив автокорреляционную функцию на выходе $P(z)$ и осуществив ее спектральную факторизацию:

$$P(z)P(z^{-1}) = \frac{\alpha z^{-1}}{1-\beta z^{-1}} \cdot \frac{\alpha z}{1-\beta z} = \Phi_{+}(z) \Phi_{-}(z)$$,

где компонент $\Phi_{+}(z) = \frac{\alpha}{1-\beta z^{-1}}$ содержит все нули и полюса внутри единичного круга, а $\Phi_{-}(z) = \frac{\alpha}{1-\beta z}$ -- вне.

Из факторизации находится $H_w(z) = \Phi_{+}^{-1}(z)$ -- всегда стабильный и каузальный выбеливающий фильтр.

В данном случае:

$$H_w(z) = \alpha^{-1}(1-\beta z^{-1})$$
$$H(z) = z$$

Исходя из выражения для $H(z)$, мы не можем отбросить некаузальные компоненты. Однако, если положить $H^{*}(z) = 1$, то в результате получится, что

$$ H_w(z)H^{*}(z)P(z) = z^{-1} $$

Иными словами, спецификация $S(z) = 1$ не может быть удовлетворена, однако может быть выполнена спецификация $S^{*}(z) = z^{-1}$, почти совпадающая с исходной.

В общем случае, импульсная характеристика $H(z)$ раскладывается в убывающий ряд:

$$H(z) = C(z)H^{-1}_w(z) = \sum_{i=0}^k h^{+}_i z^{-i} + \sum_{i=-\infty}^{-1} h^{-}_i z^{-i}$$

причем $|h^{-}_i| > |h^{-}_{i-1}|$.

Таким образом, выбрав $S^{*}(z) = z^{-\Delta}$, можно получить конечную аппроксимацию заданной точности:

$$H^{*}(z) = \sum_{i=0}^k h^{+}_i z^{-i-\Delta} + \sum_{i=-\Delta}^{-1} h^{-}_i z^{-i-\Delta} \approx H(z)$$

2. Реальне железо.

Выше установлено, что для оптимального управления интегратором $P(s)=k/s$ необходимо:

- охватить его отрицательной обратной связью с коэффициентом $\lambda/k$,

- входные воздействия пропустить через КИХ фильтр $C(z) = \alpha^{-1}(1-\beta z^{-1})$.

Положим, что $T = 0.015, k = 250, \lambda=5$, тогда мы реализуем систему:

Моделирование в Simulink на входном воздействии $u(t)=30 h(t)$, где $h(t)$ -- единичная функция, дает предсказанный результат:

Теперь проверим все это в железе. В нашем распоряжении есть частотник LG серии iS7, работающий в режиме полного векторного управления, энкодер на 500 меток на оборот и двигатель на 1,5 кВт. Система управления реализована на синтезируемом процессоре NIOS в FPGA Altera Cyclone II. Частота дискретизации 15 мс, установка скорости вращения осуществляется по шине Modbus.

Это реакция на сигнал $u(t)=30 h(t)$ без фильтра-компенсатора $C(z)$.

Вот реакция на $u(t)=30 h(t)$ с полностью реализованным регулятором.

В целом, совпадает с предсказанным теорией :)

3. Более общие мысли

Пусть у нас есть объект управления $P$ и спецификация на систему $S$. Синтез управления состоит в том, чтобы найти такой стабилизатор $C$, для которого верно $P \circ C = S$, где $\circ$ -- некоторая композиция объекта управления и контроллера. Т.е. синтез стабилизатора -- это на самом деле декомпозиция (факторизация) спецификации $S$ с выделением $P$.

Если рассматривать временную область, то очень хорошо когда $S=1$, т.е. контроллер представляет собой инверсию объекта управления $P$. Но такое редко возможно, потому как не всегда $P$ инвертируем, и в реальности на него действуют внешние неконтролируемые возмущения.
Тогда имеет смысл рассматривать приближенную факторизацию: т.е. синтез такого $C^{*}$, что $C^* \circ P = S^*$, где $S^{*}$ -- приближение к $S$ по некоторой мере $\mu(S,S^{*}) \le \epsilon$.

Реальный интерес представляют гетерогенные системы, где пространство состояний -- декартово произведение дискретных и непрерывных множеств состояний. Частный случай -- переключаемые системы управления (Switching Control). Тут возникает множество проблем, начиная с того, что основные понятия теории управления (устойчивость, наблюдаемость, etc) должны быть расширены с учетом того, что мы имеем иерархический процесс -- где непрерывная система не может достичь заданного состояния, мы заменяем ее не другую (как, например, в коробке скоростей).

Работы такого рода имеются. Это активно развивающаяся область. Наверное, я напишу что-то сюда в этом ключе в ближайшее время.

Кстати, отличное введение в гибридные системы -- этот курс лекций

Немного о логике

2010-01-07T14:52:00.000-08:00

> Логика также определяется как наука о правильном мышлении [отсюда]

Я часто вижу это определение. И оно вызывает отторжение.

1. Во-первых, что значит "правильное"? Мы можем говорить о "правильности" только в смысле какой-то метрики: насколько рассматриваемый процесс близок к какому-то идеалу.

Например, если взять нечеткую логику и в качестве функции принадлежности для высказывания "x -- положительное" выбрать:

то тогда норма может быть записана как-то так:

И в пределе при такая нечеткая логика переходит в классическую детерменированную.

Если метрику можно как-то определить, то как определить идеал? Какое мышление является абсолютно "правильным"?

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

На мой взгляд, интересным примером к сказанному может быть Парадокс Холла

3. Во многих ситуациях мышление -- в самом деле задача распознавания. Мы не долго думаем, когда встречается какая-то стандартная ситуация, а просто извлекаем из памяти некоторый шаблон поведения и применяем его. Если ситуация нестандартная и попадает под множество таких "шаблонов", то опять же мы применяем некоторую метрику и определяем какому "шаблону" ближе всего соответствует анализируемое событие. Вероятно, таким образом мыслят юристы, когда применяют законы. ;-)

4. Что же такое логика в самом деле? Логика -- это не более чем математический объект. Некоторые виды логики действительно могут быть хорошим моделями рассуждений, но только моделями. Классическая логика мало подходит для моделирования мышления, однако она безусловно играет исключительную роль в технике и математике.

Вообще мы привыкли, что математика построена на классической логике. Но было бы забавно придумать и использовать такие конструкции, которые бы основаны на других вариантах логики, например на нечеткой. Например, теория групп, результаты которой получены нечетким выводом и переходящая в обычную классическую теорию групп при предельном значении параметра (как в п.1). Разумеется, такая структура вряд ли будет полезна для анализа чего-то существующего, но например можно было бы построить нечеткую в этом смысле теорию Галуа для описания корней нечетких многочленов.
Вероятно такой подход применим для анализа каких-нибудь процессов реального мира (социология, экономика). Может быть кто-то такое делал, но я еще не видел... :-)

Что главное нужно знать, чтобы "крутить желесски":

2009-09-09T12:17:00.000-07:00

Чтобы разрабатывать электронику нужно, в первую очередь, держать в голове две простые идеи:
1. Не обязательно понимать как работает то, что ты применяешь в своих схемах. Главное точно знать, что оно делает, и что ему для этого нужно.
2. Все электронные компоненты являются расходными материалами. Даже самые дорогие. Даже печатные платы.

ПС: Кто-то конечно скажет сейчас, что так думают только быдло-схемотехники :-D

On semidefinite liftings)

2009-09-07T12:47:00.000-07:00

Пытаясь в недавнем диалоге выяснить до чего все-таки додумались в методах полуопределенной релаксации для задач выполнимости (Semidefinite Relaxation for Satisfiability), я нашел аналогию с тривиальным.

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

Вообще, такое умеет каждый школьник, потому что он знает формулу включения-исключения))

Возьмем функцию в ДНФ, определенную на . Разделим , где .

Если , то . Поскольку задана в ДНФ, то и

Написав формулу включения-исключения:

.

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

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

Jim Williams -- The art and science of analog circuit design

2009-08-12T21:39:00.001-07:00

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

@ books.google.com

On a general set of adaptive controllers))

2009-07-11T22:23:00.000-07:00

Однажды во время дискуссии по адаптивному управлению была высказана мысль, что, в общем случае, контроллер адаптируется к объекту управления и/или к внешним возмущениям, но адаптация ко входному сигналу -- абсурдна. Я возразил, что нельзя вообще говорить "невозможно" или "абсурдно" в инженерии. :-) Но этот довод не подействовал, и я вынужден был показать пример. Простой и интересный.

Рассмотрим такую ползную вещь, как частотное управление электроприводом. У нас есть сигнал , и с помощью него можно довольно точно управлять частотой вращения двигателя . Собственно, в этом функция частотника.

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

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

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

Очевидно, что оптимальное по времени управление выглядит именно так -- в виде трапеции. В этом случае вал двигателя быстрее всего повернется в заданное положение . Можно было бы вычислить , , и просто осуществить поэтапное изменение скорости на входе частотника , т.е. реализовать разомкнутое управление (open-loop control). Но поскольку на реальную систему позиционирования действуют внешние возмущения в виде неидеальности передаточной характеристики частотника, проскальзывания в редукторе и т.д., то необходимо замкнутое управление. В этом случае, мы имеем сигнал , который снимается с датчика положения на валу двигателя и который формирует сигнал ошибки .

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

Для начала вычислим время, необходимое на перемещение:

отсюда:

Теперь заметим, что по прошествию времени и скорость должна начать снижаться и:

С другой стороны, на выходе пропорционального регулятора имеем:

Из двух последних равенств получаем:

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

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

Я бы не стал писать такие простые вещи, если бы не задумывался об управлении в самом широком смысле. В сущности, современная теория управления рассматривает регулятор как отображение , в векторном пространстве последовательностей состояний объекта управления в векторное пространство последовательностей сигналов управления . Возникает два фундаментальных вопроса:

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

- дано множество управлений , какое множество неопределенностей стабилизирует .

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

Quick and dirty PID

2009-06-01T12:41:00.000-07:00

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

Что можно придумать в этом случае? Если не известна динамика, то лучше от нее избавиться. Зная передаточную функцию объекта управления , мы можем определить (или подобрать в реальных условиях) предельное время реакции объекта управления на входное воздействие . Тогда переходя от времени дискретизации для к получаем тривиально . Стабилизирующим для является регулятор с передаточной функцией:

Еще почему SAT \in P?

2009-05-04T00:02:00.001-07:00

Потому что можно показать, что . ;-)

Пусть задана булева функция , представленная в КНФ. Обозначим задачу выполнимости . Тогда эквивалентна последовательности задач на проверку предиката , которая приводит к очевидному жадному алгоритму:
0.
1. Если , то выход.
2. До тех пор, пока не
3. Взять какую-нибудь переменную и доопределить ее, получив формулы и . Если , то , иначе .

Что это дает нового? Фактически, ничего нового. Однако, есть мнение, что если задача в пересечении NP и co-NP, то она имеет полиномиальное решение. Это верно для всех P, в т.ч. и для PRIMES. С факторизацией целых чисел (FACTOR) та же ситуация, но полиномиальный алгоритм не известен. ;-)

Fuzzy Feedback Control

2009-03-27T00:05:00.000-07:00

Жосткий гон на управление с применением нечеткой логики:
Crisp Control Is Always Better Than Fuzzy Feedback Control

Автор говорит, что нечеткое управление -- паразитический метод, используемый быдло-инженерами, которые никогда не учили теорию управления :-D

Что я могу сказать? Имхо, он не так далек от правды. Я эксперементировал с нечеткой логикой для управления электроприводом, и на мой взгляд, ее применение во многих случаях является неоправданным, поскольку стабильные результаты получаются только для простых линейных систем (первого и второго порядков).

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

Convex optimization vs SAT

2009-03-11T16:28:00.000-07:00

1. Задача выпуклой оптимизации (да и вообще все что находится в этой области -- линейное, полуопределенное программирование и т.д.) отличается тем, что имеет строго единственное решение. Грубо говоря, именно по-этому выпуклая оптимизация и является легкой задачей. ;-)

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

2. Другая проблема в том, что для выпуклой оптимизации глобальный оптимум совпадает с локальным. Как сделать такое для SAT? Пусть минимум некоторой целевой функции соответствует выполняющему набору булевой формуы (можно показать, что целевая функция может быть полиномом 6-ой или 4-ой степени). Необходимо "деформировать" ландшафт этой функции таким образом, чтобы она была достаточно гладкой и без локальных минимумов. Такое можно сделать (привет топологам ;-)), однако при этом необходимо задать стационарную точку (которая, к несчастью, является искомым глобальным минимумом). Можно ли как-то исхтриться еще?

О связи теории и практики

2009-01-26T15:23:00.001-08:00

Все-таки, меня неизменно забавляет, что знак тензорного произведения называется "лампочка", сколько бы я раз это не слышал :-D

Re: Hamiltonian cycle in Digraph with degree bound two

2009-01-15T21:33:00.000-08:00

Вот этот человек написал работу, в которой утверждает, что NP=P. Ссылка на сабж содержится пунктом 38 известного линк-листа.

Прочитал статью с интересом. Речь идет про гамильтонов контур в ориентированном графе со степенью вершин не больше двух (DHCP_deg2).

Доказательство NP-полноты этой задачи было получено в 70-х годах Яном Плесником (J.Plesnik). Эту работу я не читал, но известно, что ее рецензировал небезызвестный Ершов. Сразу была мысль, что на самом деле (ограничение на степень вершин кажется очень сильным).

Однако, если взять задачу (3-SAT) выполнимости формулы , где -- дизъюнкция трех переменных, то можно сконструировать такие отображения , , , что граф содержит гамильтонов контур тогда и только тогда, когда . Это легко сделать, если в качестве подграфов брать такие конструкции:

Короче, что имеем в обсуждаемой статье!? Если перефразировать рассмотренный там алгоритм в терминах задачи выполнимости, то предложено буквально следующее:

0. Положить (константа зависит от способа вычисления совершенного паросочетания, можно полагать, что ).
1. Для всех : положить , если после этого число выполненных скобок формулы увеличилось, то новое значение сохранить, иначе -- продолжить.

(Тут: -- множество переменных задачи, -- значение переменной )

Как по мне, то очень глупо. А жаль... ;-/

Педагогическайа поэма

2009-01-15T19:47:00.000-08:00

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

Однако, пообщавшись с одним человеком, который только закончил изучение этого курса, я пришел к выводу, что электронику нужно давать не только по-другому, а вообще по-другому ;-) ВУЗовский курс не отвечает на те вопросы, которые возникают перед инженером непосредственно во время работы над продуктом. Электроника переполнена подробностями про функционирование разных элементов и схем, но, прямо скажем, не многие, прослушавшие этот курс вообще понимают зачем это и для чего.

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

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

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

Для цифрового управления тут же возникают вопросы параллельной и последовательной организации вычислений. Соответственно ПЛИС и микропроцессоры. Также смешанные идеи -- SOC и прочие извраты. Понятно, что никто не будет давать в общем курсе схемотехники программирование на языках C/C++, или Verilog/VHDL. Надо просто чтобы люди четко представляли, что такое ПЛИС, а что такое микроконтроллер, DSP, и какие бывают и где это нужно. А по поводу программирования сабжа -- можно ограничиться тем, как сгенерировать соответствующий код (для ПЛИС или МК) из Matlab-а ;-)

Кроме того, сразу встают задачи аналого-цифрового и цифро-аналогового преобразования. Тут, на мой взгляд, нельзя рекомендовать что-то лучшее, чем обзорные лекции от Analog Device. Попутно можно рассмотреть операционные усилители -- это довольно просто для изучения (если не вдаваться в подробности) и полезно.

Понимание импульсных систем целиком базируется на идеи ШИМ и использовании ключевых электронных компонентов. Тут рассматривается транзистор, полевик, IGBT (все в ключевых режимах и без физики). В качестве примеров, взять усилитель класса D и частотный преобразователь для электропривода (хотя бы на функциональном уровне).

На последок можно уделить внимание системам питания электронных устройств. Сначала про общие вопросы: дерево питания, фильтрация и блокировка. Потом чуть схем: выпрямители, классические интегральные стабилизаторы, Step-Up и Step-Down импульсные преобразователи.

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

Простое объяснение

2008-12-24T00:56:00.000-08:00

Подумалось тут про простое понимание почему задача SAT может быть решена эффективно.

Нам надо раскрыть скобки в выражении , где -- дизъюнкция (сумма переменных).
Проблема состоит в том, что если перемножать (как это учат делать в школе ;-) ) две скобки , то число слагаемых в произведении . Если -- среднее число слагаемых в скобке, то при перемножении скобок получаем порядка слагаемых. Кроме того, когда мы будем умножать, допустим, последнюю скобку, то нам необходимо выполнить порядка -- т.е. наивный алгоритм экспоненциально сложен как по времени, так и по объему памяти.

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

Можно ли вообще достичь такого? В принципе, получить подобное сжатие физически возможно. Например, любой полином с рациональными коэффициентами отображает бесконечное число точек плоскости во множество своих коэффициентов... Надо только придумать это для дизъюнктивных сумм. ;-)

Реализация интерфейса CAN в микроконтроллере NIOS

2008-11-13T01:35:00.000-08:00

Введение

Шина CAN (Control Area Network) предназначена для управления разнообразным оборудованием, в первую очередь в области промышленной автоматизации и конечно же в автомобильных системах.
Материалов о CAN относительно много, поэтому я не буду что-то пытаться пересказать. Замечу, что действительно хорошим иллюстрированным введением в CAN является презентация от Atmel.

Нас интересует следующая задача -- как связать синтезируемый процессор NIOS с шиной CAN.

Вариантов может быть несколько:

1. Написание контроллера CAN с нуля,
2. Использование решения с OpenCores,
3. использование готовых IP-Core (например, от CAST).

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

В условиях быстрого макетирования, наиболее логичным является выбор варианта 2. Далее рассмотрим применение контроллера CAN с OpenCores совместно с процессором NIOS.

По проекту "CAN Protocol Controller" необходимо сделать некоторые замечания:

1. На эту корку нет никакой документации. Но в действительности она является клоном контроллера SJA1000 от Philips, на который доступен даташит. Вот комментарий автора по этому поводу.

2. Несмотря на то, что заявлена совместимость с WISHBONE, заставить работать корку с этой шиной так и не удалось.

CAN Protocol Controller с поддержкой Avalon

Что предлагается полезного:

- из корки удалена интерфейсная часть для поддержки 8051 и Wishbone, вместо этого контроллер напрямую можно подключить к шине Avalon.

- написан простой код для NIOS, который отсылает через корку данные в шину на ID=0x20000 в режиме EFF CAN 2.0B и принимает обратно на ID=0x0.

- написан тривиальный код для Atmel AT90CAN128, принимающий данные на ID=0x20000 и отсылающий обратно на ID=0x0.

Главный модуль can_avalon имеет следующие входы и выходы:

bus_Address -- адрес шины Avalon
bus_ChipSelect -- CS шины Avalon (без инверсии)
bus_Read -- RD шины Avalon (без инверсии)
bus_Write -- WR шины Avalon (без инверсии)
bus_WriteData -- данные на запись шины Avalon
bus_ReadData -- данные на чтение шины Avalon

clk_i -- тактовая частота,
rst_i -- вход сброса (без инверсии),
rx_i -- вход данных шины CAN,
tx_o -- выход данных шины CAN,

Сигналы bus_off_on, clkout_o, irq_on -- можно не подключать (последний можно при желании подключить к входу запроса прерывания шины Avalon)

Для тестирования написана простая библиотека функций (CANLib.c, CANLib.h), содержащая следующий процедуры:

void Config_CAN2B_EFF() -- конфигурирует CAN контроллер для работы в режиме EFF CAN 2.0B;

int SendDataPacket(int ID, unsigned char *Data) -- передает данные на заданный ID (причем параметр ID функции и реальный пересылаемый по шине ID_BUS связаны ID_BUS = ID << 21 -- т.е. передаются только ID[28]-ID[21]);

int RecieveDataPacket(int* ID, unsigned char *Data) -- принимает пакет, возвращая данные и ID (блокирующая процедура, про значение ID -- тоже самое, что и в SendDataPacket);

int ReadDataPacket(int* ID, unsigned char *Data) -- считывает состояние приемного буфера;

unsigned char IsDataPacketAvailable() -- возвращает 1, если в приемном буфере хранится несчитанное сообщение (для работы совместно с функцией ReadDataPacket);

void ClearRxBuffer() -- отчистка приемного буфера.

Для использования процедур необходимо в CANLib.c определить константы:

ADDR_CAN_BASE -- базовый адрес контроллера в системе NIOS,

ACCEPT_ADDR1, ACCEPT_ADDR2 -- биты ID[28]-ID[21] фильтра принимаемых пакетов,

CAN_TIMINGX -- константы таймингов, задающие скорость передачи (подробнее в документации на SJA1000)

Результаты
По использованию ресурсов Cyclone II для can_avalon получилось:
Logic Cells: 1867
LC Registers: 1139
Memory Bits: 320

Вот как это выглядит в железе (для FPGA использована плата DE2, в качестве CAN-трансиверов -- SN65HVD232D).

Вот осциллограммы (пакет в AVR от NIOS и эхо-ответ).

Исходники
Все для NIOS
(там несколько проектов: CANSystem.qpf -- тот, который тестировался в железе; он содержит в себе NIOS от проекта CANHost.qpf, для которого написан софт в папке software)

Исходник для AVR

OpenCores 10/100 Ethernet MAC vs Altera LAN91C111

2008-11-09T16:06:00.001-08:00

Казалось бы, LAN91C111 -- вещь с мозгами, "Non-PCI Ethernet Single Chip MAC + PHY", но при этом для ее подключения к FPGA требуется в 2+ раза больше выводов, чем для обычного PHY. Также ее драйвер для uC/OS-II занимает чуть больше места в памяти (что весьма удивительно). Прибавить сюда еще стоимость и доставаемость этой микросхемы ($25 в розницу против $7 за PHY типа DP83848CVV).

Приведу результаты по использованию ресурсов FPGA двух модулей: OpenCores 10/100 Ethernet MAC -- свободно распространяемый модуль (см. niosforum), реализующий Ethernet MAC с интерфейсом Avalon, которому для счастья нужно только PHY; и модуля LAN91C111 Interface из SOPC Builder, который на самом деле является тривиальным и все что он делает -- подключает сигналы от Avalon Tristate Bridge к LAN91C111.

1. OpenCores 10/100 Ethernet MAC (eth_ocm)

Логические ресурсы:
Logic Cells: 2878
LC Registers: 1457
Memory Bits: 47360

Программа на основе шаблона simple_socket_server:
Program size (code + initialized data): 282 KBytes

Число задействованных выводов ПЛИС:
20

2. Altera LAN91C111 Interface

Логические ресурсы:
Logic Cells: 113
LC Registers: 96
Memory Bits: 0

Программа на основе шаблона simple_socket_server:
Program size (code + initialized data): 290 KBytes

Число задействованных выводов ПЛИС:
56

Как видно, выбор между обычным PHY и LAN91C111 не однозначен.
1. Почти 3000 логических ячеек для eth_ocm -- не очень большие по современным меркам, но затраты. Зато значительно меньше выводов FPGA задействовано для организации Ethernet, отсюда меньше проблем с разводкой платы и целостностью сигналов. Микросхема Ethernet PHY оказывается несколько дешевле и меньше по габаритам, чем LAN91C111.
2. LAN91C111 -- проверенное решение, не требующее никаких логических ресурсов FPGA, драйвер которого занимает почти столько же памяти, что и для eth_ocm. О недостатках сказано выше.

Лично я обычно применяю в практике PHY с использованием eth_ocm. Работает стабильно. Никаких нареканий по функционированию нет.

Некоторые сведения из силовой электроники :-))

2008-10-21T12:25:00.000-07:00

• Стоимость разработки импульсного преобразователя напряжения считается так: 1 € за 1 Вт мощности в нагрузке.

• Кабель для электродвигателя выбирается таким образом, чтобы за него электродвигатель можно было поднять.

Запретить топологию! :-)))

2008-07-07T11:48:00.000-07:00

Действительно, зачем инженерам, программистам, офисным сотрудникам, рабочим и т.д. знать, например, что такое бутылка Клейна или как вывернуть сферу наизнанку!
ban_topology
Жесть! ;-))

Про выполнимость. Немного алгебры.

2008-07-07T11:15:00.000-07:00

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

Попробуем применить алгебраический подход к сабжу NP-полноты. :-)

Нотация

– комбинаторная задача,

– конечное множество алфавита задачи , ,

– отношение на ,

– операция на множестве , ,

– множество отношений на , заданных условием задачи ,

– множество операций на .

Основная идея подхода.

Комбинаторная задача описывается структурой отношений на множестве .

Что на входе

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

Определения

Пусть , определим вектор , такой что , . Множество замкнуто по , если для всех , .

Определим следующие морфизмы:

, – множество всех операций, на которых замкнуты все отношения .

, – множество всех отношений, которые замкнуты на всех .

Как найти ?

Из определения отношения , замкнутого по операции , непосредственно следует, что:

где произведение определяется следующим образом: если , где – операция на множестве и для , то .

Частный случай 3SAT: для и определение по множеству представляет собой задачу выполнимости, содержающую переменных.

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

Какова природа ?

Очевидно, что все должны быть отображениями, замкнутыми относительно композиции [1]. В таком случае, содержит по крайне мере одну из следующих обобщенных операций:

1. Константную операцию : .

2. Идемпотентную бинарную операцию , которая не является прямым отображением: , , .

3. Мажоритарную операцию : .

4. Операцию паритета : – элементарная абелева 2-группа.

5. Операцию полуотображения : , , .

6. Все операции, являющиеся унарными : , .

Вычислительная сложность.

Если структура задачи пораждает множество операций , то используя известные результаты теории сложности [2] для разных классов задач, можно доказать следующие свойства:

1. Если , то может быть решена с константными затратами памяти.

2. Если – ассоциативна и коммутативна, то .

3. Если , то .

4. Если , то .

5. Если , а также , где , то .

6. Если , то .

PS

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

1. Maurice Pouzet, Ivo G.Rosenberg. Small clones and the projection property Архив
2. Lewis, H. R. and Papadimitriou, C. H. Elements of the Theory of Computation, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 1997. DjVu

Про выполнимость. Общие слова.

2008-07-01T06:20:00.000-07:00

Мы не можем разрешить NP-трудную задачу на тьюринговой машине в полиномиальное время и с полиномиальными затратами памяти. Что мы можем? Если не тьюринговая машина, то что? Что делает задачу неразрешимой?...

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

Вопросы очень общны. И нетривиальны. Я попробую немного порассуждать в будущих записях об этой проблеме, тем более, что с кое-какими вещами я знаком и в теории и на практике. Заранее извиняюсь за может быть не очень строгое изложение -- не чувствую себя формалистом по духу ;-))

Про эмо

2008-06-12T14:35:00.000-07:00

Anthropic Computing

>> There is at least one foolproof way to solve 3SAT in polynomial time: given a formula , guess a random assignment , then kill yourself if does not satisfy . Conditioned on looking at anything at all, you will be looking at a satisfying assignment! Some would argue that this algorithm works even better if we assume the many-worlds interpretation of quantum mechanics. For according to that interpretation, with probability 1, there really is a universe in which you guess a satisfying assignment and therefore remain alive. Admittedly, if is unsatisfiable, you might be out of luck. But this is a technicality: to fix it, simply guess a random assignment with probability , and do nothing with probability . If, after the algorithm is finished, you find that you have not done anything, then it is overwhelmingly likely that is unsatisfiable, since otherwise you would have found yourself in one of the universes where you guessed a satisfying assignment...

Подробнее:
http://www.scottaaronson.com/talks/anthropic.html
http://www.scottaaronson.com/papers/npcomplete.pdf

Первая запись

2008-04-27T03:17:00.001-07:00

Здравствуйте!
Я начинаю ведение блога, в котором буду публиковать свои заметки по проектированию железа, цифровой обработке сигналов и прикладной математике.