Уменьшение данных журнала для канала передачи данных с переменной пропускной способностью

Question

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

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

1. Система будет хранить минимальное и максимальное значения в течение 10 мс.
2. Система внутренне поставит в очередь ограниченное число (скажем, 50) этих пар данных.
3. Не допускается потеря минимальных или максимальных значений, но временной интервал, в котором они возникают, может варьироваться.
4. Когда очередь заполнится, соседние пары данных будут объединены, начиная с конца очереди, так что преобразованные пары min/max теперь представляют интервалы 20 мс.
5. Схема должна быть итерационной, чтобы при необходимости выполнялось дальнейшее объединение интервалов до 40 мс, 80 мс и т. Д.
6. Схема должна быть линейно взвешена по всей длине очереди, чтобы не было объединения для самых новых данных и максимально необходимого объединения самых старых данных.

Например, с очередью длиной 6, последовательное сокращение данных должно заставить пары данных покрывать эти интервалы:

initial: 10 10 10 10 10 10  (60ms, queue full)
 70ms:   10 10 10 10 10 20
 80ms:   10 10 10 10 20 20
 90ms:   10 10 20 20 20 20
100ms:   10 10 20 20 20 40
110ms:   10 10 20 20 40 40
120ms:   10 20 20 20 40 40
130ms:   10 20 20 40 40 40
140ms:   10 20 20 40 40 80

Новые образцы добавляются слева, данные считываются справа.

Эта идея, очевидно, относится к категориям сжатия с потерями и разреженного кодирования.

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

Я намеренно упростил и упустил другие вопросы, такие как отметка времени.

Вопросы:

1. Уже есть алгоритмы, которые делают этот вид регистрации данных? Я не ищу стандартные алгоритмы сжатия изображений или изображений с потерями, но что-то более специфичное для регистрации данных, как описано выше.
2. Что будет наиболее подходящей реализацией для очереди? Связанный список? Дерево?

Answer 1

Вы ищете термин "сжатие с потерями" (см.: http://en.wikipedia.org/wiki/Lossy_compression). Оптимальный метод сжатия зависит от различных аспектов, таких как распределение ваших данных.

Answer 2

Определите функцию комбинированной стоимости, которая соответствует вашим потребностям, например (len(i) + len(i+1)) / i^2, затем итерируйте массив, чтобы найти "самую дешевую" пару для замены.

Answer 3

Как я понимаю, вы хотите передать min() и max() всех выборок за период времени.

например. Вы хотите передавать мин / макс каждые 10 мс с взятием проб каждые 1 мс?

если вам не нужны отдельные образцы, вы просто сравниваете их после каждой выборки

i=0; min=TYPE_MAX; max=TYPE_MIN;// First sample will always overwrite the initial values
while true do
    sample = getSample();
    if min>sample then
        min=sample

    if max<sample then
        max=sample

    if i%10 == 0 then
        send(min, max);
        // if each period should be handled seperatly: min=TYPE_MAX; max=TYPE_MIN;
done

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