Rapid Balise Telegram Decoder with Modified LFSR Architecture for Train Protection Systems
We propose a novel balise telegram decoding scheme for RFID-based high-speed train protection systems. To reduce the amount of position errors by minimizing the decoding latency, the proposed scheme enables the decoder to have opportunities to find a valid telegram during single balise passage by reutilizing the values from previous failures. We also present a modified linear-feedback shift register (LFSR) and parallel connection of LFSR units to complete both error detection and synchronization of telegrams in one cycle. The experimental results show that the proposed scheme achieves approximately 2,000 times faster error detection and synchronization than traditional architectures.
BALISES are one of the most important components of the recent train protection systems, as they transmit movement authorities and trackside data (e.g., position reference, speed limits, and maintenance works on the line) to trains, which are the sources of position markers and movement authorities – . Fig. 1 shows the typical on-board transmission equipment having the antenna unit and balise transmission module (BTM) function, which communicates with the European train control system (ETCS) kernels . In general, balises are tele-powered via an inductively coupled signal transmitted by the on-board transmission equipment during train passage and returning the telegram message including safety-related information.
In this work, we propose a novel balise telegram decoding architecture for high-speed trains to increase the decoding speed. As the telegram can be corrupted by electromagnetic interference and crosstalk, movement authorities and trackside data are transmitted after undergoing scrambling, substitution with a symbol code, and addition of checksum for parity checks and synchronization. We focus on minimizing the processing latency required to calculate the remainder of the polynomial division for parity checks and synchronization, maintaining a low computational complexity. The proposed scheme enables the decoder to have additional opportunities to find a valid telegram during single balise passage by reutilizing the essential information from the previous decoding failures. We also propose a modified linear-feedback shift register (LFSR) architecture and parallel connection of two LFSR modules to complete both error detection and synchronization in only one cycle. We then analyze the telegram missing probability, processing latency, and complexity of the proposed structure.
Balise Telegram Encoding:
The user data contain a header (50 bits) and optional packets (variable length). The number of allowed packets depends on the telegram format. To avoid burst errors, random bit errors, and bit slip/insertion, the user data are scrambled and substituted with a symbol code of different Hamming distance and a checksum is added for parity checks and synchronization. Consequently, the telegram format in a binary polynomial
b(x) = bn-1Xn-1 +….. +b1x + b0 …………………..(1)
consists of shaped data, control bits, scrambling bits, extra shaping bits, and check bits, where n = 1023 (long format) or 341 (short format) indicates the length of telegram:
- Shaped data (b1022 … b110 or b340 … b110) contain the user data (830 bits or 210 bits) after scrambling and substitution.
- Control bits (b109 … b107) include inversion bit and spare bits, which are set to 001. Scrambling bits (b106 … b95) are the initial state of the scrambler that operates on the data bits before shaping.
- Extra shaping bits (b94 … b85) are used to enforce the constraints on check bits independent of the scrambling.
- Check bits (b84 … b0) include 75 parity bits of the error correcting code and 10 bits for synchronization. Check bits shall be defined as
b84X84 +….. +b1x + b0
= Rf(x)g(x)[ bn-1Xn-1+……+ b84X84]+o(x) ……(2)
where f(x) = fmxm + … + f1x + f0, g(x) = gkxk + … + g1x + g0, and o(x) = g(x) depend on the telegram format. Ra(x)[b(x)] denotes the remainder of the division of b(x) by a(x).
Balise Telegram Decoding:
The on-board transmission equipment stores the received telegrams in a telegram buffer. Assume that the total number of received bits is N (N ≥ n), which depends on the speed of the train and the contact length between the on-board equipment and balise.
Figure 1: Moving window based sequence update
After receiving the first n bits, the telegram decoder starts to capture an n-bit sequence c(x) = cn–1x n–1 + … + c1x + c0 from the telegram buffer in Fig. 1. c(x) is a cyclically shifted version of the transmitted telegram b(x), except for random or burst bit errors. Any balise telegram receiver shall be at least as good as the following basic receiver operation:
1) Consider a window of n + r consecutive received bits (long format: r = 77; short format: r = 121. If the window has already been shifted over 7,500 bits, set r = n).
2) Is the parity-check satisfied, i.e., are the first n bits divisible by g(x)? If not, shift window and go to step 1.
3) Do the r additional bits (rightmost in the window) coincide with the first r bits (leftmost in the window)? If not, shift the window and go to step 1.
4) Find the beginning (position of bn–1) of telegram with the help of f(x). If Rf(x)[c(x)] is an impossible value, go to step 1.
5) Are all 11-bit words (bn–1 … bn–11), (bn–12 … bn–22), …, (b10 … b0) valid? If not, shift the window and go to 1.
6) At this point, the telegram is considered safe.
7) Is the inversion bit b109 = 1? If yes, all of the received bits could be used after inversion.
8) Check the other two control bits. If b108 = 1 or b107 = 0, abort with the message unknown telegram format.
9) Invert the 10-to-11-bit transformation and de-scramble.
10) Output the user bits and the original state of the inversion bit (b109).
Figure 2: The conventional telegram decoder architecture
In this paper, we focus on reducing the processing latency and computational complexity required for error detection (step 2) and synchronization (step 4).1 In general, these procedures are accomplished by sequentially calculating the remainder of the division of c(x) by g(x) and f(x), respectively,
e(x) = Rg(x)[c(x)]=ek-1xk-1 +…… + e1x+e0 (3) and
s(x) = Rf(x)[c(x)]=sm-1xm-1+…………..+s1x+s0 (4)
Fig. 2 depicts the error detection and synchronization steps of the conventional receiver. For a given n-bit sequence c(x), the error detection unit (EDU) calculates e(x) to determine whether the parity-check is satisfied. If an error is detected (e(x) ≠ 0), c(x) is updated by shifting the window, as shown in Fig. 1. Otherwise, the synchronization unit (SU) calculates s(x) to find the beginning of the telegram. If s(x) is an impossible value, i.e., s(x) = 0, c(x) is updated by shifting the window. Otherwise, the telegram b(x) can be obtained by cyclically shifting c(x) with the help of s(x) and the look-up table (LUT), which stores the corresponding number of bits elapsed since the beginning of the telegram. Whenever the train passes a balise, the receiver repeats this procedure until it finds a valid telegram. The valid telegram is then converted to user data after the validation of all symbol codes (step 5), the confirmation of control bits (steps 7 and 8), code substitution and descrambling (step 9).
Figure 3 : Conventional LFSR architecture
The window may be shifted by either one or several bit positions at a time. Let us specify the window shift size as s bits. For a given total number of received bits N, decreasing s allows the telegram receiver to have additional opportunities to find a valid telegram at the cost of increased processing latency. The conventional telegram decoder normally uses the LFSR-based architecture to calculate e(x) and s(x), which is widely applied in modern communication systems. Fig. 3 shows the typical structure of the LFSR for calculating e(x). Before starting each calculation, each register in the LFSR should be initialized to 0, i.e., ei = 0 (i = 0, …, k – 1). The current sequence c(x) is then entered into the LFSR by inserting its coefficients one by one in descending order. In other words, the coefficient ci (i = 0, …, n – 1) is added to the LSB of e(x), i.e., e0. At the same time, the MSB of e(x), i.e., ek–1, is added to the other coefficients ei (i = 0, …, k – 1) if the corresponding gi (i = 0, …, k – 1) is 1. This feedback path is disconnected when the corresponding gi is 0. As a result, this LFSR implementation requires n cycles to calculate e(x) and s(x), respectively. As the basic receiver is designed to execute error detection and synchronization steps sequentially, it uses at least 2n cycles to complete steps 2 and 4. For example, it takes 2,046 cycles for error detection and synchronization of long format (n = 1023), causing the large amount of position error of high-speed trains. The parallel LFSR architecture may reduce the processing latency; however, it requires more hardware resources for storing intermediate values. As the train control systems should be tolerable to the various error sources, numerous fault-tolerable solutions including the triple modular redundant scheme are employed by duplicating the primitive processing units. Considering the additional complexity, therefore, the previous parallel LFSR structure cannot be accepted for the practical embedded solution. We introduce a novel telegram decoding architecture in the next section to efficiently reduce the processing latency without increasing the hardware cost.
- More Speed in Decoding process
- Having More electromagnetic interference and crosstalk
- Not added checksum for parity checks
Proposed Telegram Decoding Algorithm:
The proposed telegram decoding algorithm allows n-bit sequence c(x) to be updated by one bit whenever the EDU determines that the parity-check is not satisfied or the SU fails to find the beginning of the telegram. In addition, the proposed algorithm does not require initialization of the registers in the LFSR before starting the calculation of the updated sequence. Instead, it reutilizes the remaining values stored in the registers. These values are the results of the previous calculation.
Let cu(x) denote the updated sequence after a 1-bit window shift. cu(x) can be derived from c(x) as follows:
Cu(x) = Cnew + xc(x) – Cn-1Xn ………….. (5)
where cnew is the new bit entered into the LSB side of the window, xc(x) is 1-bit window shift, and cn–1x n is the removal of the expired MSB of the previous sequence. Calculation of the remainder eu(x) from cu(x) can be rewritten as follows:
eu(x) = Rg(x)[cu(x)]
=cnew + Rg(x)[xc(x)] – Rg(x)[cn-1xn]. ……….(6)
cnew is simply added to the other terms. Let us assume that c(x) = qe(x)g(x) + e(x), where qe(x) is the quotient polynomial. The second term in (6), i.e., Rg(x)[xc(x)], is then derived as
Rg(x)[xc(x)] = Rg(x)[xqe(x)g(x)+xe(x)]
= Rg(x)[xe(x)] = xe(x) – ek-1 g(x). ….(7)
This means that remaining values stored in the LFSR, e(x), can be reused to calculate the second term in (6). Specifically, all of the coefficients of e(x) are shifted by one to form xe(x), and the divisor g(x) is then subtracted from xe(x) if the order of the polynomial e(x) is k – 1, i.e., ek–1 = 1. Let us assume that
r(x) = Rg(x) [xn] = rk-1 xk-1 + ….. + r1x + r0 …..(8)
Because r(x) does not depend on cu(x), it can be pre-calculated. The third term in (6), i.e., Rg(x)[cn–1xn ] = cn–1Rg(x)[xn ] = cn–1r(x), is then subtracted from the other terms if the expired MSB of the previous sequence equals 1, i.e., cn–1 = 1. Otherwise, Rg(x)[cn–1xn ] = 0. Finally, eu(x) can be simplified as
eu(x) = cnew + xe(x) – ek-1g(x) – cn-1 r(x) ….(9)
Similarly, calculation of the remainder su(x) for the updated sequence cu(x) can be rewritten as follows:
Su(x) = Rf(x) [Cu(x)]
= Cnew + Rf(x)[xc(x)-Rf(x)[cn-1xn] …(10)
= cnew + xs(x) – sm-1 f(x) – cn-1 p(x),
p(x) = Rf(x)[xn] = pm-1 xm-1 + … + p1x + p0 (11)
The proposed telegram decoding algorithm reduces the processing latency and computational complexity considerably because it takes only one cycle to calculate eu(x) and su(x) for the updated sequence cu(x) by reutilizing the remaining values stored in the LFSRs after previous calculations.
Modified LFSR Architecture:
Figure 4: Modified LFSR architecture supporting the proposed telegram decoding algorithm
We propose a novel LFSR architecture that allows us to adopt the proposed telegram decoding algorithm based on the conventional LFSR architecture presented in Section II. Fig. 4 illustrates the proposed LFSR architecture for the EDU. The upper part of the proposed LFSR architecture is related to the calculation of the second term in (9), which is identical to the conventional LFSR architecture shown in Fig. 3. The lower part of the proposed LFSR architecture is superimposed for the calculation of the fourth term in (9). Only one cycle is needed to calculate eu(x) from the updated sequence cu(x) because it reutilizes the remaining values stored in LFSR. Without loss of generality, the LFSR architecture for SU can be obtained in a similar manner.
Single-Cycle Telegram Decoding Architecture:
We further propose a single-cycle decoding architecture for simultaneous error detection and synchronization for decrease the processing latency. Fig. 6 depicts the single-cycle telegram decoding procedure of the proposed architecture. Using the LFSR architecture proposed in Section III-B, both the EDU and SU require only one cycle to calculate e(x) and s(x) from sequence c(x).
Figure 5: Single Cycle telegram decoding of the proposed algorithm
If the EDU determines that the parity- check is not satisfied or the SU fails to find the beginning of the telegram for a given c(x), the MSB of the current sequence cn–1 is expired and the new bit cnew is entered into the LSB side to form a new sequence cu(x). If both operations are completed with valid results, i.e., eu(x) = 0 and su(x) ≠ 0, b(x) can be obtained by cyclically shifting the current sequence using su(x) and the LUT. Whenever the train passes each balise, the decoder repeats this procedure until it finds a valid telegram.
- Less Speed in Decoding process
- Having less electromagnetic interference and crosstalk
- Added checksum for parity checks
 System Requirements Specification, Chapter 7 ERTMS/ETCS language, Ref. SUBSET-026, ver 3.4.0, European Union Agency for Railways Std., Dec. 2014.