Showing posts with label check-matrix. Show all posts
Showing posts with label check-matrix. Show all posts

12 March 2021

Rus PSK4 1200Bd: solved

The questions related to the "nature" of the 1022-bit period of the QPSK 1200Bd signal (see the previous post) has been solved thanks to the help of my friend cryptomaster: I was waiting for traffic ("I tuned it waiting for traffic, but luckless until it went off") but actually it was already there!
He had the great intuition to reshape the bitstream into di-bit symbols, ie 2 bits per row given the 4ary modulation, then we gone on analyze the two columns separately and found the m-sequence x^9+x^5+1 (or the equivalent x^9+x^4+1) in the second column: therefore, each bit of data is followed by one bit of the m-sequence, ie the 1022-bit period consists of 511 bit of data interleaved with the 511 bit of the sequence generated by the LFSR x^9+x^5+1 (Figure 1).

Fig. 1 - x^9+x^5+1 sequence in the 2nd column
 
The next step was to see if the same polynomial is to some extent involved in the bits of the first column. Based on the ninth degree of the polynomial x^9+x^5+1, a 9x511 parity check matrix was constructed, assuming that an H(511,502) code - based on that same polynomial - is used in the fomation of the bits of column #1. Notice that  a H(m,k) code is a Hamming code that encodes k bits of data into m bits (the codeword), adding m-k parity bits (CRC). 
Our parity matrix consists of a 9x502 check sub-matrix and a 9x9 identity sub-matrix (Figure 2):
 
Fig. 2 - Hamming parity check (511,502) matrix

As you know, the CRC formation is carried out by comparing column-by-column the k bits of each data row in turn with all the (m-k) rows of the check sub-matrix and counting the "vertical" correspondences of the "1"s of the data row and the r-row of the check sub-matix: if the count is odd then the CRC bit #r will be set to "1", otherwhise will be set to "0". That way, the (m-k) bits of the CRC is appended to the k bits of the data row just examined and the computation go ahead with the next data row.
That said, the bitstream of column #1 (the file demod-bit1.txt) has been reshaped to form a 511-column matrix of codewords. Manually checking the about two hundred 511-bit length codewords would have been a nightmare, so I wrote a short Octave script that would do the job for me and calculate the 9-bit CRC of each row along with a simulation of the final PSK4 modulation - the result in Figure 3.
 

Fig. 3 - 9 bit CRC rows (left); PSK4 modulation of data +CRC (right)

By comparing the calculated CRC bits (Figure 3 on the left) with the bit stream of column n. 1 (Figure 4), it is clear that each row of the bitstream is nothing more than a "codeword" consisting of 502 bits for data plus 9 bits for Hamming CRC, ie the 511-bit period that we saw.

Fig. 4 - the bistream of column #1

My friend cryptomaster tested also a 2016 recording and found it matches with the above conclusions (Figure 5). For what concerns the nature of the 502-bit strings of data they are probably telecontrols, further recordings are need. A possible (!) functional block diagram of the modulator is shown in Figure 6.
 
Fig. 5
 

14 August 2018

LINK-11 SLEW, Systematic CRC check matrix

In Link-11 SLEW the error detection encoding is applied to all 48-bit data words within each type of field with the exception of the EOM field. The encoding scheme uses Cyclic Redundancy Check (CRC) H(60,48) which is generated using a 12-bit Shift Register defined by the polynomial x12 + x10 + x8 + x5 + x4 + x3 + 1, and producing the Link-11 SLEW 60-bit (48+12) encoded frames.
Quoting STANAG-5511 Annex-B §11.1.1.1 "The data is shifted serially into the Shift Register starting with the most significant bit (MSB) until the least significant bit (LSB) has been applied to the input stage of the Shift Register. This accomplishes a division of the data by the polynomial that defines the Shift Register. The remainder of the division is represented by the values in each stage of the Shift Register: these 12 values are appended to the data bits as parity, creating a systematic code".
Systematic codes have the advantage that the parity data can simply be appended to the source block, and receivers do not need to recover the original source data if received correctly since they are located in the leftmost bits of the received data (this explains because systematic code is also called “Separable”). The standard CRC encoder is different from the Systematic CRC encoder in the way the encoded word is calculated, therefore the data bits cannot be separated from encoded word before decoding takes place. 

In my opinion, actually STANAG-5511 seems to describe the "systematic CRC decoder" rather than the "systematic CRC encoder": indeed, the decoder just works by getting the input encoded word, which might contain errors, and dividing it by the generator polynomial to get the remainder (i.e. calculating E(x) mod G(x) and getting R(x)). If remainder of division is zero then the encoded word has no errors, otherwise error is detected with a non-zero remainder [1]. 
That said, the systematic generator matrix is obtained by selecting as rows the codewords associated with the 12-bit fields 100000000000, 010000000000, ..., and 000000000001. Well, my friend cryptomaster worked on the 4095-bit maximum-length sequence produced by the generator polynomial x12 + x10 + x8 + x5 + x4 + x3 + 1 obtaining the 12-row 60-column parity-check matrix that is shown below
                                
111100110100011000110111111001001001110101100010 100000000000
011110011010001100011011111100100100111010110001 010000000000
110011111001011110111010000111011011101000111010 001000000000
111001111100101111011101000011101101110100011101 000100000000
100000001010001111011001011000111111001111101100 000010000000
110000000101000111101100101100011111100111110110 000001000000
011000000010100011110110010110001111110011111011 000000100000
010000110101001001001100110010001110001100011111 000000010000
110100101110111100010001100000001110110011101101 000000001000
100110100011000110111111001001001110101100010100 000000000100
110011010001100011011111100100100111010110001010 000000000010
111001101000110001101111110010010011101011000101 000000000001

If an error is detected with a non-zero remainder, the error can be corrected just using the check matrix. 
Code verification is carried out by comparing each line of encoded data in turn with all rows of the check sub-matrix: the vertical correspondences of the "ones" locations in the encode line and in the row #n of the check sub-matrix are counted. If the matches are even then the CRC bit #n will be "0", otherwhise (ie matches are a odd number) the CRC bit #n will be "1".

Let's try a verification for the first 48-bit data in Fig.1

Fig. 1

48-bit data                                                                    12-bit CRC
111011100101011011110011001001101010001000010100 011000011001
111100110100011000110111111001001001110101100010 check sub-matrix row #1
14 matches (even), CRC bit value: 0

111011100101011011110011001001101010001000010100 011000011001
011110011010001100011011111100100100111010110001 row #2
11 matches (odd), CRC bit value:  1

111011100101011011110011001001101010001000010100 011000011001
110011111001011110111010000111011011101000111010 row #3
17 matches (odd), CRC bit value:  1

111011100101011011110011001001101010001000010100 011000011001
111001111100101111011101000011101101110100011101 row #4
16 matches (even), CRC bit value: 0

111011100101011011110011001001101010001000010100 011000011001
111001111100101111011101000011101101110100011101 row #5
16 matches (even), CRC bit value: 0

111011100101011011110011001001101010001000010100 011000011001
100000001010001111011001011000111111001111101100 row #6
12 matches (even), CRC bit value: 0

111011100101011011110011001001101010001000010100 011000011001
011000000010100011110110010110001111110011111011 row #7
10 matches (even), CRC bit value: 0

111011100101011011110011001001101010001000010100 011000011001
010000110101001001001100110010001110001100011111 row #8
11 matches (odd), CRC bit value:  1

111011100101011011110011001001101010001000010100 011000011001
110100101110111100010001100000001110110011101101 row #9
11 matches (odd), CRC bit value:  1

111011100101011011110011001001101010001000010100 011000011001
100110100011000110111111001001001110101100010100 row #10
16 matches (even), CRC bit value: 0

111011100101011011110011001001101010001000010100 011000011001
110011010001100011011111100100100111010110001010 row #11
12 matches (even), CRC bit value: 0

111011100101011011110011001001101010001000010100 011000011001
111001101000110001101111110010010011101011000101 row #12
13 matches (odd), CRC bit value:  1

as expected, the 12-bit CRC added to the first 48-bit frame is:
011000011001.

If you want try by yourself, the last 60-bit sequence consisting of all "ones" could be a segment of the picket EOM and no error detection or correction bits are applied to this field! (Link-11 fileds will be treated in a next post).
Notice that Link-11 SLEW uses also 1/2 rate and 2/3 rate convolutional encoders to improve the reliability of the system, while CLEW does not use convolutional encoders and employs Hamming (30,24) encoding with the overall parity bit:
https://i56578-swl.blogspot.com/2018/08/link-11-clew-hamming-check-matrix.html 

That said, and if me and cryptomaster are right, STANAG-5511 is not so clear in the pages related to CRC Data Encoding.

https://yadi.sk/d/C-GO-nbl3aBYKr
https://yadi.sk/d/l_2IQJrP3aBYbV

[1] http://www.ecs.umass.edu/.../SystematicCRChelp.html

4 August 2018

LINK-11 CLEW, Hamming check matrix

The check of a Link-11 CLEW stream discussed in the end part of this post, can be speed up by using the Hamming parity check matrix for the H(30,24) coding, ie a 30-bit code word consisting of 24 bits for data + 6 bits for Hamming parity bits (termed EDAC in Link-11 literature). The check matrix is constructed as shown in MIL 188-203-1A #5.2.4.1 and here.

 
Code verification is carried out by comparing each line of code in turn with all rows of the parity check matrix, except the extra parity line (the overall parity bit): the vertical correspondences of the "1" locations in the code line and in the row #n of the check sub matrix are counted. If the matches are even then the correspondent location #n in the EDAC bits will be "1", otherwhise (ie matches are a odd number) will be "0" (odd parity).
 
 
  EDAC           data
110100 000001110101110001100010
010011 111001110010010001111011
110100 111100101110010110011111
100100 010111010000110110000110
010010 011010000000010100100111
110001 010001110110000010010000

     check sub-matrix           identity sub-matrix
111111111111100000000000 010000
111111000000011111110000 001000
110000111100011110001110 000100
001100110011011001101101 000010
101010101010110101011011 000001
111111111111111111111111 111111
Test the first line of code 000001110101110001100010

000001110101110001100010
111111111111100000000000 check matrix line #0
6 matches, EDAC bit #0 shall be 1

000001110101110001100010
111111000000011111110000 check matrix line #1
4 matches, EDAC bit #1 shall be 1

000001110101110001100010
110000111100011110001110 check matrix line #2
5 matches, EDAC bit #2 shall be 0

000001110101110001100010
001100110011011001101101 check matrix line #3
6 matches, EDAC bit #3 shall be 1

000001110101110001100010
101010101010110101011011 check matrix line #4   
5 matches, EDAC bit #4 shall be 0
EDAC bits 0-4: 11010

Test the second line of code 111001110010010001111011

111001110010010001111011
111111111111100000000000 check matrix line #0
7 matches, EDAC bit #0 shall be 0

111001110010010001111011
111111000000011111110000 check matrix line #1
8 matches, EDAC bit #1 shall be 1

111001110010010001111011
110000111100011110001110 check matrix line #2
7 matches, EDAC bit #2 shall be 0

111001110010010001111011
001100110011011001101101 check matrix line #3
9 matches, EDAC bit #3 shall be 0

111001110010010001111011
101010101010110101011011 check matrix line #4   
10 matches, EDAC bit #4 shall be 1

EDAC bits 0-4: 01001
The verification of the remaining combinations confirms the use of the same method of checking (if you want, you can check it yourself).

If only one error is detected, it is corrected and sent to the computer. The computer is also advised that the word contained an error and that it is corrected. If two errors are detected the Hamming decoding can only determine that errors exist but cannot determine which bits are in error.

16 July 2018

LINK-11 CLEW, conventional waveform


The 16 tone frequencies used by CLEW are 605 Hz (used for Doppler correction), 2915 Hz (used for data and synchronization) and 935, 1045, 1155, 1265, 1375, 1485, 1705, 1815, 1925, 2035, 2145, 2255, and 2365 Hz. All information is conveyed by DQPSK modulation at symbol rate of 75 or 45.45 Baud of the 15 data subcarriers tones (Doppler tone remains unmodulated), each of the tone represents 2 data bits and then resulting in a total of 30 data bits consisting of Control Code frames and Data Message frames(M-series messages). The tone at 935 Hz corresponds to bit locations 0 and 1, last tone at 2915 corresponds to bit locations 28 and 29.
Sometimes you may see CLEW using simultaneously the USB and LSB (ISB): indeed, identical signals are transmitted on in ISB and at the receiver both the sidebands will be separately and independently deodulated.  A means is provided to allow operator selection of USB, LSB or the diversity operation (DIV) modes:
  • DIV: data words derived from the diversity combination of the USB and LSB will be provided to the tactical computer. This mode of operation is used to help combat multipath interference.
  • Automatic: the receiving station automatically selects the version that represents the best information available from the USB, LSB or DIV version of the received data word.
When the criteria do not establish a clear choice, the DIV version is selected.  

The three control codes which are used to operate a Link-11 net are the Start Code, Stop Code, and Address Code, each consisting of two encoded 30-bit frames. The Start Code is the first two frames of the transmitted data message while the two frames Stop Code immediately follows the last message frame to signify the end of the data. There are two stop codes according to the transmitting station: Control Stop Code (transmission from the data net control station, or DNCS) is a 2 frames consisting of all "zeros", and Picket Stop Code (transmission from a picket station) which consists of a 2 frames consisting of all "ones". 
The Start Code is the first two frames of the transmitted data message while the two frames Stop Code immediately follows the last message frame to signify the end of the data. There are two unique stop codes according to the transmitting station:
  • Control Stop Code (transmission from the data net control station, or DNCS) is a 2 frames consisting of all "zeros",
  • Picket Stop Code (transmission from a picket station) is a 2 frames consisting of all "ones".
Each net partecipating unit is identified by the Address Code which immediately follows the Control Stop Code if the DNCS transmits data.

Fig. 1 - Link-11 data segment
The Data Message frames (Figure 2) follow the Start Code and contain tactical information. Each Data Message frame consists of 30 bits composed of a 24-bit word provided by the tactical computer and 6 Hamming parity bits (bit locations 24 through 29) provided by the modem. The Hamming parity bits are used by the receiver modem for error detection and correction, for this reason they are also refferred to as EDAC bits. Only Data Messages contain Hamming parity bits: Start, Stop, and Address codes are not Hamming parity encoded.
Notice that the 24-bit words may be optionally encrypted using KG-40 crypto device which just sits in midlle between tactical computer and modem. 

Fig. 2 - Link-11 Data Message frames
The six EDAC bits are encoded as follows:
  • Bit 29 is set such that when added to bits locations in 11 through 23, the number of ones will be an odd number;
  • Bit 28 is set such that when added to bits locations in 4 through 10 and 18 through 23, the number of ones will be an odd number;
  • Bit 27 is set such that when added to bits in locations 1,2,3,7,8,9,10,14,15,16,17,22, and 23, the number of ones will be an odd number;
  • Bit 26 is set such that when added to bits in locations 0,2,3,5,6,9,10,12,13,16,17,20, and 21, the number of ones will be an odd number;
  • Bit 25 is set such that when added to bits in locations 0,1,3,4,6,8,10,11,13,15,17,19,21, and 23,the number of ones will be an odd number;
  • Bit 24 is set such that when all the bits of the frame are added, the number of ones will be an odd number. Bit 24 is called the overall parity bit. 
Figure 3 shows a check of the first six 30-bit frames of the Data Message in Fig.2

Fig. 3

30 May 2018

T207_test

Finally a useful and fast tool to check the presence of T207 encoding in FSK bitstreams. The tool T207_test runs on Octave, a programming language for scientific computing, and was originally - and roughly - coded by me and then optimized and speeded-up by Christoph:

The script builds a n x 14 test matrix and for each row computes the number of "1" bits in the first 12 columns; then check if the 13-14 bits value is the one expected according to the table below. Since the 2-bit 'checksum' can occur everywhere within the 14-bit frame, the stream is shifted up to 14 times building a new test matrix at each shift. The script counts the success checks for each test matrix and display the results. The better test matrix is also plotted along the frame start offset (ie after how many shifts).