Article directory
- Preface
- 1. m sequence
-
- 1. Generation of m sequence
- 2. Properties of m sequence
-
- ①.Balance
- ②. Run distribution
- ③、Shift addition characteristics
- ④.Autocorrelation function
- ⑤.Power spectral density
- ⑥. Pseudo noise characteristics
- 2. M sequence
-
- 1. Generation of m sequence
- 2. Properties of m sequence
- 3. m sequence in MATLAB
-
- 1. MATLAB code of m sequence generation function
- 2. MATLAB simulation
Foreword
Random noise in communication systems can cause distortion in analog signals and bit errors in digital signals, and it is also an important factor limiting channel capacity. Therefore, people often hope to eliminate or reduce random noise in communication systems.
Additionally, sometimes one wishes to obtain random noise. For example, when testing the performance of communication equipment or systems in a laboratory, a certain amount of random noise may be deliberately added.
Pseudo-random noise has certain statistical properties similar to random noise and can be generated repeatedly. Because it has the advantages of random noise and avoids the disadvantages of random noise, it has been increasingly widely used in practical applications. The currently widely used pseudo-random noise is derived from periodic digital sequences after filtering and other processing. We will later refer to this periodic sequence of numbers as a pseudo-random sequence. It is sometimes called pseudo-random signal and pseudo-random code.
1. m sequence
1. Generation of m sequence
The m sequence is short for Longest Linear Feedback Shift Register Sequence. It is the longest period sequence produced by a shift register with linear feedback. Now, we first give an example of an m sequence. A 4-stage linear feedback shift register is shown in the figure below.
Generation of m sequences
Let its initial state be
(
a
3
,
a
2
,
a
1
,
a
0
)
=
(
1
,
0
,
0
,
0
)
(a_3,a_2,a_1,a_0)=(1,0,0,0)
(a3?,a2?,a1?,a0?)=(1,0,0,0), then when shifting once,
a
3
a_3
a3? and
a
2
a_2
a2? Modulo 2 addition produces new input
a
4
=
1
⊕
0
=
1
a_4=1\oplus0=1
a4?=1⊕0=1, the new state becomes
(
a
4
,
a
3
,
a
2
,
a
1
)
=
(
1
,
1
,
0
,
0
)
(a_4,a_3,a_2,a_1)=(1,1,0,0)
(a4?,a3?,a2?,a1?)=(1,1,0,0). After this shift 15 times, it returns to the initial state.
(
1
,
0
,
0
,
0
)
(1,0,0,0)
(1,0,0,0). It is not difficult to see that if the initial state is all “0”, that is, (0,0,0,0), the result obtained after the shift is still an all “0” state. This means that all “0” states should be avoided in such feedback registers, otherwise the state of the register will not change. Because there are 4 levels of shift registers
2
4
=
16
2^4=16
24=16 possible states. In addition to the all “0” state, only 15 states are available. This means that the sequence produced by any 4-stage feedback shifter has a maximum period of 15.
We often want to generate as long a sequence as possible using as few series as possible. It can be seen from the above example that, generally speaking, the longest period that may be generated by an n-level linear feedback shift register is equal to
(
2
n
?
1
)
(2^n-1)
(2n?1). We call this longest sequence the maximum length linear feedback shift register sequence, or m sequence for short.
2. Properties of m sequence
①、Balance
In a cycle of the m sequence, the number of “1”s and “0”s is essentially equal. To be precise, the number of “1”s is one more than the number of “0”s.
②. Run distribution
We call the consecutive (connected) elements in a sequence that have the same value a “run”. The number of elements in a run is called the run length. For example, the m sequence given in the figure above can be rewritten as:
In one cycle (m elements), there are 8 runs in total, among which there is one run with length 4, namely “1 1 1 1”, and one run with length 3, namely “0 0 0”, with length There are two runs of 2, namely “1 1” and “0 0”, and there are 4 runs of length 1, namely two “1”s and two “0”s.
Generally speaking, in an m sequence, a run of length 1 accounts for 1/2 of the total number of runs; a run of length 2 accounts for 1/4 of the total number of runs; and a run of length 3 accounts for 1/8. Strictly speaking, the length is
k
k
The number of runs of k accounts for the total number of runs
2
?
k
2^{-k}
2?k, of which
1
≤
k
≤
(
n
?
1
)
1\le k\le (n-1)
1≤k≤(n?1). And the length is
k
k
During the run of k (where
1
≤
k
≤
(
n
?
2
)
1\le k\le (n-2)
1≤k≤(n?2)). The runs of “1” and “0” are divided equally.
③、Shift addition characteristics
one
m
m
m sequence
M
p
M_p
Mp? is another different sequence produced by any number of delayed shifts
M
r
M_r
Adding Mr? modulo 2 still gives
M
p
M_p
A certain delayed shift sequence of Mp?
M
s
M_s
Ms? That is:
M
p
⊕
M
r
=
M
s
M_p \oplus M_r=M_s
Mp?⊕Mr?=Ms?
④, Autocorrelation function
The figure below shows the autocorrelation function of the m sequence. The dots in the figure represent
j
j
When j is taken as an integer
ρ
(
j
)
\rho(j)
ρ(j) takes a value, and the polyline is
R
(
τ
)
R(\tau)
Continuous curve of R(τ). It can be seen that the two overlap. It can also be seen from the figure that when the period
T
0
T_0
T0? Very long and symbol width
T
0
/
m
T_0/m
T0?/m extremely small
R
(
τ
)
R(\tau)
R(τ) approximates the impulse function
δ
(
t
)
\delta(t)
The shape of δ(t).
Autocorrelation function of m sequence
It can be seen from the above that the autocorrelation function of the m sequence has only two values: 0 and (1/m). Sometimes we call this type of sequence with only two values of the autocorrelation function a double-valued autocorrelation sequence.
⑤, power spectral density
Performing Fourier transform on the autocorrelation function of the m sequence can obtain its power spectral density.
The power spectral density of the m sequence
⑥. Pseudo-noise characteristics
Because the equilibrium, run distribution and autocorrelation characteristics of the m sequence are very similar to the basic properties of random sequences, the m sequence is usually called a pseudonoise (PN) sequence, or a pseudo-random sequence.
2. M sequence
The sequence with the longest period produced by the Nonlinear Feedback Shifter is called the M sequence. It is different from the m sequence above, which is the longest period sequence produced by a linear feedback shifter.
From the analysis of the m sequence generator, it can be seen that an n-level m sequence generator can only have
(
2
n
?
1
)
(2^n-1)
(2n?1) different states. But n-level shift registers can have at most
2
n
2^n
There are 2n states, and all “0” states cannot appear in the m sequence. Under linear feedback conditions, the generator’s state will not change after the all “0” state appears; but under nonlinear feedback conditions, this is not necessarily the case. Therefore, the longest period of the nonlinear feedback shift register can be
2
n
2^n
2n, we call this period up to
2
n
2^n
The sequence of 2n is the M sequence.
1. Generation of m sequence
Refer to the above m sequence generation diagram, which is an n=4-level m sequence generator. Its 15 states are shown in the figure. If you add a “000” status to it, it can become an M sequence generator. Because the subsequent state of the shift register must be shifted in from its previous state, the “0000” state must be before the initial state “1000” and after the “0001” state. That is to say, we need to modify its recursion equation into a nonlinear equation, so that after the “0001” state is substituted into the new recursion equation, the state “0000” (instead of “1000”) is generated, and the state “0000” is substituted into Then produce the state “1000” (instead of leaving “0000” unchanged).
2. Properties of m sequence
The M sequence is similar to the m sequence and also has noise properties to a certain extent. It satisfies the first two of the m sequence:
- In one cycle of the M sequence, the number of “0” and “1” occurrences is equal
- In a cycle of an n-level M sequence, there are total runs
2
n
?
1
2^{n-1}
2n?1, where the length is
k
k
The length of k accounts for
1
/
2
k
1/2^k
1/2k,
1
< k ≤ n ? 2 1
4-stage M-sequence generator
Compared with m-sequences, the main advantage of M-sequences is their large number, that is, the total number of translationally inequivalent M-sequences that can be generated by a shift register with the same level n is much larger than that of m-sequences, and it increases rapidly with the increase of n. Increase. A comparison of the number of series n with the number of two possible sequences that can be generated is given in the table below.
3. m sequence in MATLAB
1. MATLAB code of m sequence generation function
mseq.m
function [mout] = mseq(n, taps, inidata, num)
%************************************************ ***************
% n: order n of m sequence
% taps: The connection location of the feedback register
% inidata: initial value sequence of register
% num: The number of m sequences output
% mout: output m sequence, if num>1, then each line is an m sequence
%************************************************ ***************
mout = zeros(num,2^n-1);
fpos = zeros(n,1);
fpos(taps) = 1;
for ii=1:2^n-1
mout(1,ii) = inidata(n); % output value of register
temp = mod(inidata*fpos,2); % Calculate feedback data
inidata(2:n) = inidata(1:n-1); % shift the register once
inidata(1) = temp; % update the value of the first register
end
if num > 1 %If you want to output multiple m sequences, generate other m sequences
for ii=2:num
mout(ii,:) = shift(mout(ii-1,:),1);
end
end
2. MATLAB simulation
function code = mseq(n, taps, init, len)
code = mseq(3,[1 3],[1 1 1],52); disp(code);
- The parameter n represents the order of the m sequence, that is, the length of the sequence is
2
n
?
1
2^n-1
2n?1. The input parameter n must be a positive integer.
- The argument taps is a one-dimensional vector specifying the coefficients of the feedback polynomial used to generate the m sequence. These coefficients indicate whether the terms in the polynomial participate in feedback. For example, if taps are [1 3], the feedback polynomial is
1
+
z
3
1 + z^3
1 + z3, where z represents the delayed operation of the sequence.
- The parameter init is a one-dimensional vector specifying the initial state of the m sequence. The length of the vector must be less than or equal to n. If the length of init is less than n, it is prepended with zeros.
- The parameter len represents the length of the m sequence to be generated.
You can see the following results:
The generated code is of type 52 × 7 double:
1 1 1 0 1 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 1
1 0 0 1 1 1 0
0 1 0 0 1 1 1
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 0 1 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 1
1 0 0 1 1 1 0
0 1 0 0 1 1 1
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 0 1 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 1
1 0 0 1 1 1 0
0 1 0 0 1 1 1
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 0 1 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 1
1 0 0 1 1 1 0
0 1 0 0 1 1 1
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 0 1 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 1
1 0 0 1 1 1 0
0 1 0 0 1 1 1
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 0 1 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 1
1 0 0 1 1 1 0
0 1 0 0 1 1 1
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 0 1 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 1
1 0 0 1 1 1 0
0 1 0 0 1 1 1
1 0 1 0 0 1 1
1 1 0 1 0 0 1
1 1 1 0 1 0 0
0 1 1 1 0 1 0
0 0 1 1 1 0 1
My qq: 2442391036, welcome to communicate!