Рейтинг
12.57
голосов: 10

О блоге

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

Администраторы (1)

Модераторы (0)

Модераторов здесь не замечено

Читатели (152)

dcoder Krieger Tabke XANDER marvin_yorke kest Vga Alatar mzw kalvenolt Reverb mist grand1987 Gornist Rom kvm labor neiver Leopoldius rumkin

Все читатели блога

Каскадное кодирование Рида — Соломона\Витерби.

Речь идет о реализации а не описание алгоритмов. За описаниями алгоритмов в гугл. Они все открыты и очень хорошо расписаны.

Под реализацией понимается — реализация для микроконтроллеров. А не для DSP, PC, FPGA и прочих кодировщиков.


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

Криптография для эмбеддера. Введение в ассиметричные алгоритмы.



У меня в черновиках «завалялась» небольшая статья по ассиметричной криптографии. Статья коллеги a9d приводит пример использования «модульной арифметики», (правда в другом ключе) но не объясняет «как это работает». Т. к. коллега запретил комментарии к своей статье (ИМХО, зря, в комментариях самое вкусное), я позволю себе опубликовать данную недоработанную статью.


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



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

Асимметричное шифрование. RSA это очень просто.

Раньше я уже искал либы для микроконтроллера с реализацией Асимметричное шифрования, но ничего путевого не нашел. Я делал главную ошибку. Я искал в рунете! Я постоянно натыкался на посты где трындели, что это очень сложно и микроконтроллер не потянет. Так вот, это П***шь и его потянет даже avr.

И бла бла бла. В общем первые же поиски на англоязычных сайтах увенчались успехом.


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

Преобразуем в строку. Часть 2. Числа с фиксированной и плавающей точкой.

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

В качестве чисел с плавающей точкой использован 32-х разрядный float.



Читать дальше
  • +14
  • 07 января 2013, 13:08
  • neiver
  • 1

Спасаем стек

Продолжим тему о микроконтроллерах с малым объёмом памяти. Я обычно подразумеваю под таковыми те, у которых ОЗУ 512-1К. Есть, конечно и со 128, и 256 байтами, но там уже не до СИ. При использовании ОС, которая умеет в переключение нитей, возникает проблема памяти для стека, тем более, что у каждой нити он свой. Стек расходуется в основном на две вещи (помимо контекста при переключении нитей): сохранение регистров и выделение фрейма при вызове функций. Соответственно, чем глубже вложенность вызовов, тем больше расходуется стек. Неприятные сюрпризы могут вылезти при использовании библиотечных функций, таких как printf (лол, никогда не знаешь, что там внутри, хотя, можно и посмотреть для интереса).


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

Перевод статьи "The Bare Metal Enthusiast: I can C clearly".

Просматривая статьи на одном новостном ресурсе, увидел перевод, который мне очень понравился.
Нашел оригинал статьи. Оказалось, в блоге автора были еще несколько статей. Переводом одной из них я и хочу с вами поделиться. Предназначена она в первую очередь для тех, кто только начал писать для микроконтроллеров, написал несколько программ и столкнулся с ощущением «поверхностности» знаний, почерпнутых из руководств вроде «быстрый старт». По крайней мере у меня возникал вопрос: «Ну умею я настраивать АЦП, таймеры, прерывания и дергать ногами МК. А что такое архитектура программы и как её выбирать? Почему код, напечатанный в книгах, отличается от кода, который я вижу в исходниках?».

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

сам перевод.
  • +4
  • 14 декабря 2012, 13:38
  • do_sl

Алгоритм Брезенхэма. Моя реализация.

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


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

Быстрое Преобразование Фурье, java

Решил я вплотную подступиться к Цифровой Обработке Сигналов.
Достаточно долгое время не мог понять, как реализовать алгоритм БПФ. Математика была понятна, но просмотрев готовые решения, понять как они работают не удавалось. На какое-то время необходимость в этом отпала, а потом снова появилась.
Ко второму заходу опыта программирования стало уже немного большое, и, наверно, поэтому мне удалось самому написать программу, выполняющую БПФ на java (код без особого труда можно портировать на C++ или C).
Я не буду выводить основные формулы и доказывать, что они верны — с этим справляются на многих сайтах и во многих книжках (по крайней мере лично у меня это не вызвало трудностей).
Основные формулы1

Я просто расскажу о том, как пользуясь этими формулами я писал саму программу, с какими трудностями столкнулся и как их преодолел.
Статья, по сути предназначена для тех кто:
1. Прочитал и понял математику, стоящую за БПФ.
2. Понял алгоритм бит-реверса.
3. Понял почему граф преобразования выглядит именно так

Первое, что я сделал — поставил основную задачу «Разработать программу быстрого преобразования Фурье на java». Затем приступил ко второму этапу: сбору информации. Прочитав доказательства и поняв математику, стоявшую за алгоритмом, я понял, следующие вещи:
1. Алгоритм можно спроектировать пользуясь парадигмой Divide and Conquer.
2. В данной парадигме задачу можно решить рекурсивно или итеративно.
Рекурсивный подход, как мне кажется, в какой-то мере проще в написании и понимании, но приведет к некоторым потерям в скорости из-за вложенных вызовов методов (функций).

Напомню или расскажу тем, кто не в курсе, что парадигма Divide and Conquer (Разделяй и Властвуй) сводится к трем общим этапам.
1. Этап разделения задачи на более простые задачи меньшего размера.
2. Этап решения всех этих задач.
3. Этап объединения результатов всех меньших задач в общий результат.

БПФ же можно разбить на три основных этапа:

1. Перестановка входных отсчетов (значений в массиве). Почему это нужно много рассказывать не буду, но в общем, как я понял, это позволяет сэкономить память, т.к. в таком случае не требуется массив для хранения промежуточных результатов и в целом упрощает написание программы.
2. БПФ основано на том факте, что если N = 2^n (т.е. 1,2,4,...,1024...2^n), то N-точечное ДПФ (т.е. количество отсчетов исходных данных равно числу n) можно разбить на два ДПФ размером вдвое меньше (2^(n-1)). В этом и заключается второй этап парадигмы. Мы разбиваем ДПФ, пока не приходим к базовому случаю — ДПФ от двух отсчетов, которое сводится к сложению и вычитанию двух элементов массива.
3. Объединение результатов каждого из разбиений.

Дальше можно собственно приступать к разработке алгоритма предварительно разбив его на эти отдельные задачи.
1. Разработать метод перестановки входных отсчетов с помощью алгоритма бит-реверса.
Если непонятно почему бит-реверс, пишите в коммантариях.
Собственно алгоритм бит-реверса

i — целое число, в котором надо переставить t-битов.

private static int reverse(int i, int t) {
		// TODO Auto-generated method stub
	    int Shift = t - 1;
	    int LowMask = 1;
	    int HighMask = 1 << Shift;
	    int R;
	    for(R = 0; Shift >= 0; LowMask <<= 1, HighMask >>= 1, Shift -= 2)
	        R |= ((i & LowMask) << Shift) | ((i & HighMask) >> Shift);
	    return R;
	}


А это, собственно, перестановка значений.

for(int i = 1; i < Nmax-1; i++)
		{
		    int J = reverse(i,powerOfTwo);           // reverse ����������� ���� � I � �������� �������
		    if (i >= J)                     // ���������� ��� ��������������
		    	continue;
		    double S = array[i]; array[i] = array[J]; array[J] = S;  // ������������ ��������� xI � xJ
		}


Т.е. здесь мы берем число i, переставляя в нем биты, получаем число J. i и J — это индексы двух элементов массива, которые нужно поменять местами. Ну и меняем их местами. Повторяем эту процедуру пока не пройдемся по всем элеметам массива, т.е. пока i не станет больше или равно Nmax-1.

А дальше начинается самое интересное.

*************************************************************
Статья пока недописана, но публикую, т.к. интересуют комментарии. О чем написать подробнее, что может вызывать вопросы и пр. Любые мнения и помощь приветствуются!

Функции календаря и времени на одном регистре

На этапе разработки
Работаю я значит метрологом, работа хорошая, спокойная.Но вот не задача, некоторые приборы уж очень долго греются(где-то часа 4).Придешь в 9-00 включишь, к 13-00 прогрелись, а с 13 до 15 обед, в 17-30 уже надо собираться… так что времени на поверку совсем мало остается. А план-то делать надо.Решил я значит сделать некое подобие таймера, который включает и выключает нагрузку по расписанию и заодно следит за ТВР. Но не об этом сегодня речь.


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