Пролог

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

Самый длинный код Баркера имеет размер 13. Для преодоления помех надо закачивать в импульс существенно большую энергию. Энергию можно закачивать в двух направлениях: либо в амплитуду передаваемого сигнала, либо в длительность излучения. Амплитуду невозможно увеличивать до бесконечности. Порой амплитуду наоборот надо уменьшать, чтобы увеличить скрытность работы радара. Остается увеличивать длительность зондирующего импульса. Однако длинные монотонные импульсы портят разрешение по дальности. Чтобы не проиграть в разрешении по дальности длинные сигналы надо как-то модулировать. Вот тут-то и выходят на сцену М-последовательности.

Вот так может выглядеть радарный зондирующий 21ms импульс, модулированный M-последовательностью 000010000110001010011110100011100100101101110110011010101111110.

Теория

М-последовательность или последовательность максимальной длины ( maximum-length sequence, MLS) — псевдослучайная двоичная последовательность, порожденная регистром сдвига с линейной обратной связью и имеющая максимальный период.

М-последовательности обладают следующими свойствами

1) М-последовательности являются периодическими с периодом L=2^n-1, где n - это размер сдвигового регистра

2) Количество символов, принимающих значение 1, на длине одного периода М-последовательности на единицу больше, чем количество символов, принимающих значение 0
3) Периодическая АКФ любой М-последовательности имеет постоянный уровень боковых лепестков, равный −1/N. Периодическая АКФ, это когда на вход AKФ подан сигнал составленный из одной и той же M-последовательности. Без лишних семплов между ними.

4) С ростом N величина боковых пиков уменьшается. АКФ усечённой М-последовательности, под которой понимается непериодическая последовательность длиной в период N, имеет величину боковых лепестков, близкую к −1/sqrt(N) .

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

0101110 0101110 0101110 0101110
010 111 001 011 100 101 110 010 111 
2   7   1   3   4   5   6   2   7 

Реализация

М - последовательность можно сгенерировать при помощи сдвигового регистра с обратной связью. Регистр состоит из триггеров.

Какие конфиги есть у генератора М-последовательностей?
1) начальное состояние сдвигового регистра генератора. По сути это N-битное число. Оно может быть любым, лишь бы не быть полностью нулевым. В случае нулевого сдвигового регистра генератор будет просто генерировать одни нули.

2) Указание количества обратных связей. Очевидно, что обратных связей должно быть как минимум 1. При этом, чтобы было что с чем складывать в обратной связи по модулю два, то ёще и получается, что обратных связей должно быть минимум две. Может быть и больше.

Вот пример схемотехники реального генератора M-последовательности длинны 7.

В Си-коде генератор М-последовательности может выглядеть как функция maximum_length_sequence_get_sample

bool array_s8_shift_right(int8_t* const arr, uint32_t size, uint32_t shift) {
    LOG_DEBUG(ARRAY, "%s(): Shift:%u", __FUNCTION__, shift);
    bool res = false;
    if(arr) {
        if(size) {
            if(shift < size) {
                LOG_DEBUG(ARRAY, "ShiftNumbers:%u");
                uint32_t i = 0;
                for(i = (size - shift); shift <= i; i--) {
                    LOG_DEBUG(ARRAY, "a[%u]=a[%u]", i, i - shift);
                    arr[i] = arr[i - shift];
                }
                memset(arr, 0, shift);
                res = true;
            } else {
                memset(arr, 0, size);
                res = true;
            }
        }
    }
    return res;
}

bool array_s8_add_front(int8_t* const arr, uint32_t size, int8_t value) {
    bool res = false;
    if(arr) {
        if(size) {
            res = array_s8_shift_right(arr, size, 1); // -->
            if(res) {
                arr[0] = value;
            }
        }
    }
    return res;
}



int8_t maximum_length_sequence_get_sample(uint8_t num) {
    int8_t value = 0x55;
    MaximumLengthSequenceHandle_t *Node = MaximumLengthSequenceGetNode(num);
    if (Node) {
        uint32_t i = 0;
        int8_t new_val = 0;
        for (i = 0; i < Node->cur_size; i++) {
            new_val ^= Node->memory[i] * Node->feedback[i];
        }
        bool res = array_s8_add_front(Node->memory, Node->cur_size, new_val);
        if(res){
            value = Node->memory[Node->cur_size - 1];
            LOG_DEBUG(MAXIMUM_LENGTH_SEQUENCE, "M_SEQ_%u,Sample:%u", num, value);
            Node->spin++;
        }
    }
    return value;
}

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

Отладка

Я написал и собрал утилиту для генерации M-последовательностей. Утилита имеет такой набор команд.

-->h seq
+-----+----------+-------------------------+-------------
| Num | Acronym  |      CommandName        | Description 
+-----+----------+-------------------------+-------------
|   1 |     mssz |            m_seq_size   |    MseqSize 
|   2 |      mss |            m_seq_seed   |    MseqSeed 
|   3 |      msf |        m_seq_feedback   | MseqFeedBack 
|   4 |      msg |        m_seq_generate   | MseqGenerate 
|   5 |     msed |            m_seq_diag   |    MseqDiag 
|   6 |     msac | m_seq_auto_correlatino  | MseqAutoCorrelation 
|   7 |     msei |            m_seq_init   |    MseqInit 
+-----+----------+-------------------------+-------------

Вот справка по командам

Сгенерировать М-последовательность можно командой msg с указанием номера генератора. Предварительно надо только задать размер сдвигового регистра командой mssz.

35:29-->mssz 1 6; msg 1

2130.198,148,I,[Mseq],Num,Ok
2130.200,149,I,[Mseq],shiftRegNum,Ok
2130.203,150,I,[Mseq],M_SEQ_1,N:1,CurSz:6,MaxSz:10,Spin:1054,
Mem:1,0,0,0,0,0,FeedB:0,0,0,0,1,1,Name:MAX_LEN_SEQ1,Len:63,Init:On,
35:30-->
2130.216,151,I,[Mseq],Num,Ok
2130.220,152,I,[Mseq],ShiftReg:6,codeLen:63
000010000110001010011110100011100100101101110110011010101111110
35:30-->
35:30-->
35:31-->mssz 1 7; msg 1

2139.205,153,I,[Mseq],Num,Ok
2139.207,154,I,[Mseq],shiftRegNum,Ok
2139.210,155,I,[Mseq],M_SEQ_1,N:1,CurSz:7,MaxSz:10,Spin:1117,
Mem:1,0,0,0,0,0,0,FeedB:0,0,0,0,0,1,1,Name:MAX_LEN_SEQ1,Len:127,Init:On,
35:39-->
2139.218,156,I,[Mseq],Num,Ok
2139.228,157,I,[Mseq],ShiftReg:7,codeLen:127
00000100000110000101000111100100
01011001110101001111101000011100
01001001101101011011110110001101
0010111011100110010101011111110
35:39-->
35:44-->

Можно просмотреть диагностику генератора командой msed (m_seq_diag).

 45.208-->msed 2

46.413,130,I,[MaxLenSeq],Num,Ok
46.423,131,I,[MaxLenSeq],N:2,MAX_LEN_SEQ2,Mem:000001000000,FeedB:000001000100,CurSz:6,MaxSz:6,
46.437,132,I,[MaxLenSeq],N:2,CurSz:6,MaxSz:6,Spin:126,Mem:000001000000,FeedB:000001000100,Init:On,Name:MAX_LEN_SEQ2,Len:63,
0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,0,0,46.494,133,I,[MaxLenSeq],Diag,Ok
 46.500-->
 47.516-->
 47.675-->msed 2

48.681,134,I,[MaxLenSeq],Num,Ok
48.706,135,I,[MaxLenSeq],N:2,MAX_LEN_SEQ2,Mem:010000010000,FeedB:000001000100,CurSz:6,MaxSz:6,
48.729,136,I,[MaxLenSeq],N:2,CurSz:6,MaxSz:6,Spin:189,Mem:010000010000,FeedB:000001000100,Init:On,Name:MAX_LEN_SEQ2,Len:63,
0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,0,0,0,1,0,0,1,0,1,1,0,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,0,1,0,0,0,0,48.815,137,I,[MaxLenSeq],Diag,Ok
 48.822-->

Если посчитать АКФ одной одинокой М-последовательности, окруженной нулями, то ее боковые лепестки по модулю будут существенно превышать значение 1/N. В этом плане M-последовательности и проигрывают кодам Баркера.

А тут я посчитал кросс-кореляцию для M-последовательности длинной 127 элементов. Как можно заметить, чем длиннее M-последовательность, тем ярче выражена ее авто-корреляционная функция.

Вот так выглядит корреляция двух разных М-последовательностей одинаковой длины в 63 элемента. Высота лепестков 23 % от автокорреляции. Как по мне - это много.

Острая автокорреляция - это главное зачем используют такие коды.

Результат

Удалось научиться генерировать уникальные М-последовательности разной длинны. Написал на си консольную утилиту для генерации M-последовательностей. Посчитаны автокорреляции конкретных М-последовательностей.

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

Словарь

Источники

Вопросы
1) Сколько различных М-последовательностей можно сгенерировать на сдвиговом регистре из K триггеров?