IND USTRY SOFTWAR E

DATA COMPRESSION ALGORITHMS FOR EOL FLASH PROGRAMMING OF AUTOMOTIVE ELECTRONIC CONTROL UNITS The undesired long programming times of electronic control units (ECUs) are limited by the production cycle times. Frequently, the CAN bus with KWP on CAN or UDS on CAN is used for programming. Through the limited bandwidth the transmission of the data is the bottleneck in terms of programming time. In order to reduce these times during the production process as well as in the development phase, the usage of data compression is proposed by ZF Friedrichshafen AG and Vector Informatik GmbH. 22

HORS

DR.-ING. ACHIM FAHRNER

works as Software Developer at the Corporate Research and Development Center of ZF Friedrichshafen AG in Friedrichshafen (Germany).

DIPL.-ING. MICHAEL GEESE

is Development Engineer in the Department Electronic Control Systems at ZF Getriebe GmbH in Friedrichshafen (Germany).

DATA COMPRESSION AND EOL PROGRAMMING

Modern automotive systems consist of many different ECUs. During the production process these ECUs must be programmed with application software. The EOL (end-of-line) programming process is either done during the assembly of the final automotive system by the OEM or by the part suppliers. With the continuous increase of software complexity, the sizes of the hex files increase steadily, so today several megabytes of data have to be transmitted to the ECU. However, the time allowed for (re-)programming is limited by the production cycle times. So, long programming times cause unwanted additional costs. In many projects the CAN bus [1] is used as medium for the data transmission, for example over KWP on CAN or UDS on CAN [2]. The limited bandwidth of the CAN bus makes the transmission of the data to the bottleneck in ECU programming, not the programming of the data in the flash ROM itself. To reduce the programming time, the amount of data to transmit to the ECU should be reduced. In this article we want to discuss data compression to achieve this goal. With data compression [3, 4] the information _i is compressed by the encoder to a coded sequence _c : EQ. 1

Compression

n_ _i nc

The transmission of _c requires less bandwidth as needed for _i . In the decoder, _c is decompressed again: DIPL.-ING. ARMIN HAPPEL

is Manager and responsible for the Flash Bootloader Development at Vector Informatik GmbH in Stuttgart (Germany).

02I2010

Volume 5

EQ. 2

Decompression

n_˜ _c ni

We consider only lossless data compression algorithms, so _i˜ = _i assuming error-free transmission of the data. The data compression algorithms can be divided in the following classes: : Symbol-based algorithms, e.g. Shanon-Fano, Huffman and arithmetic coding. : Sequence-based algorithms: This class comprises runlength encoding (RLE) and the Lempel-Ziv familiy (LZ77, LZ78, LZW, LZSS etc.). : Concatenation of several algorithms: Typically, a sequencebased and a symbol-based algorithm are combined. An example is the well-known deflate algorithm [5], implemented in GNU Zip (gzip [6]). Concatenated algorithms achieve the best compression gains, if the data sizes alone are considered. However, the complexity increases through concatenation. For embedded algorithms a trade-off between compression gain and complexity must be wisely chosen. Therefore, in the automotive environment, sequence-based algorithms are often preferred. For the programming of ECUs with data compression the programming data is first compressed (“online” in the tester or “offline”) and then transmitted to the ECU, , often via the CAN bus [1, 2]. In the ECU, the data is received, decompressed and then flashed. Certain controllers exist that use compressed data in the flash. It can be seen that data compression can be incorporated without hardware changes; this means moderate costs. Systems with and without data compression can run in parallel. Data compression for programming of automotive ECUs must meet the requirements described in the following:

23

IND USTRY SOFTWAR E

EVALUATION ACCORDING TO THE COMPRESSION GAIN

The performance of the different compression algorithms can be compared with several measures. A simple one considers the data sizes before and after compression, for instance with the definition of the compression gain: EQ. 3

 ECU programming with data compression

: The limited resources of the controller must be taken into account (RAM, ROM, runtime). The decompression must be as fast and as small as possible. In particular, the handling of complex data structures in the ECU is difficult. : “Online”decompression: To achieve minimum programming times and due to the limited resources, it is not possible to buffer the complete compressed data stream. The decompression must start in parallel to the transmission of the data, thus a sliding-window or a block-oriented algorithm must be used. : Stability: The chosen algorithms should lead to good results for a broad range of projects, preferably for all projects. This means, different controllers with different compilers, different applications, small and large files, and so on. : Coding of repetitions: If parts of the overall ROM are not used, the empty ranges of the corresponding files are often filled up with a special trap code consisting of repeated short code fragments. Sometimes, the empty areas are also transmitted to the ECU. The compression algorithms must be able to compress repetitions effectively. Furthermore, patent-protected algorithms were excluded to avoid patent violations. These requirements limit the set of adequate algorithms. The usage of data compression to reduce the programming time is reasonable as long as the transmission of the data to the ECU is the bottleneckThe performance of the compression is also influenced by the different implementation possibilities of the bootloader in the ECU: : Point of time for the decompression: The decompression in the ECU can be performed after each CAN message or after one block (Transfer Data in UDS),

24

resulting in different buffer sizes and in a different software structure in the bootloader. : Parallel/Serial programming: The flash process itself can be executed in parallel or serial to the data reception. Parallel Programming saves programming time, but leads to a more complex structure of the bootloader. The security (regarding transmission errors) of a programming system employing data compression is comparable to a system without compression, if the checksums in the programming files are calculated with the uncompressed data. The tester must either be able to access the uncompressed data as well as the compressed data or at least know the checksums of this data.

Ii – Ic

G = _____ I i

where I and Ii are the sizes of the compressed and uncompressed data respectively. As an example, the following algorithms are considered: : Runlength encoding (RLE) : Lempel-Ziv 77 (LZ77) : Huffman encoding based on 8-Bit symbols (HF8) : Huffman encoding based on 16/8-Bit symbols (HF16) : LZSS(11,4) : LZSS adapted to embedded applications (LZSSa) : LZ77/LZSS variation as used as compression stage in deflate algorithm (LZV) : Deflate-algorithm (Concatenated compression: LZ77-+Huffman-compression) as implemented in GNU Zip (gzip).  shows compression gains for one particular (gearbox) project. The LZ based algorithms show superior results as com-

 Compression gains for different compression algorithms (unc. means uncompressed)

pared to the Huffman compression. The concatenated gzip shows as expected the best results. However, as the complexity is high the implementation in an ECU is difficult and it can thus only be considered as a benchmark. Furthermore, the effect of empty memory areas on the compression gain can be seen. By comparing B with C it gets clear how the performance decreases when the application data is removed. This means the application data can be much better compressed than the application code.  shows the results in terms of data sizes before and after compression. The portion of empty memory areas can be seen. It gets clear that some algorithms can deal with those empty areas better than other algorithms. The results of RLE, LZV and gzip are almost independent of the amount of empty memory areas. Additional investigations [7] showed that the controller type has a strong effect on the results: Differences up to 20 % in the compression gain could be observed between two up-to-date 32-bit controllers. This means for each new controller type the results must be reviewed. The algorithms followed yet the same tendency in terms of compression gain, independent of the controller type. So, there seems to be no need to implement several controller-dependant algorithms. Note that a higher compression gain for one controller does not imply that this controller is superior. In contrast, a higher compression gain shows that the amount of redundancy is higher. In other words, the code density must be worse (assuming identical performance of the compression algorithms for the different code). The used compiler, compiler optimizations with different compiler and assembler options can significantly influence the results. The results for different customers (with identical controller type) are close together. Similarly, the compression gains change only slightly during the development process. This means, results gained at the beginning of the project can be used as estimates for the mass production data. However, optimization steps can minimize redundancy and thus worsen the compression gains. To summarize, compression gains of about 34 % and 42 % respectively for two different 32-bit controllers could be observed with realistic algorithms, if no 02I2010

Volume 5

 Data sizes before and after compression with and without empty memory areas (unc. means uncompressed)

empty memory areas are contained in the source data. For data with empty memory areas the obtainable compression gains are higher. Dependent on the amount of empty data about 60 % can be achieved. Without application data the results are worse; for the application data alone compression gains of more than 70 % could be observed (for data without empty memory areas!). VALIDATION OF THE RESULTS WITH SIMULATION TOOLS

The compression gain (measured with the data sizes) alone is not sufficient to determine the potential saving of programming times, as the effects of tester and bootloader implementations as well as the complexity of the (de)compression are not taken into account. An algorithm with a good compression gain can, for instance, lead to long programming times, if the decompression is complex and thus runtimes are higher. The implementation of the different data compression algorithms is very time-consuming, especially if several projects with different controller types are investigated. An alternative approach is the usage of a simulation tool. With this tool, the complete transmission chain is emulated with CANoe. To obtain realistic results, the controller specific parameters for flash erasure and programming times must be known,

as well as implementation details of the bootloader and estimates of the deadtimes. Then, the different methods can be compared and the parameters can be optimized. ALTERNATIVES AND EXTENSIONS TO DATA COMPRESSION

In order to minimize the programming times of ECUs, the following techniques should additionally be taken into account: : Optimization of the flash data: As the programming times are directly affected by the sizes of the programming files, the files should be as small as possible. This can be achieved for example, by reducing the application software complexity, by code optimization and by using adequate compiler and linker optimizations. The possible savings are typically rather limited though. : Parallel programming: As described above, time can be saved by receiving data in parallel to the flash process. This should be integrated in the bootloader implementation. Parallel erasure of the next segment while programming the actual segment is another possibility. Besides, parallel programming with several CAN controllers can be advantageous. However, this leads to hardware changes in the tester and means complex data handling.

25

IND USTRY SOFTWAR E

THANKS Special thanks to the Co-Authors: Dipl.-Ing. Yacine Anouz is Master Student at the University of Applied Sciences Wiesbaden and worked as graduate at ZF Friedrichshafen AG; Dipl.-Ing. Carsten Mauer works as Team Leader at ZF Friedrichshafen AG and is responsible for the system software development for production test benches and flash

existing production facilities restrictions must be respected. The deadtimes in the tester and in the ECU as well as the protocol overhead are to be minimized, for example by using large Transfer-Data blocks. : Usage of alternative transmission protocols: Enhanced systems (e.g. Flexray) offer more bandwidth as compared to the CAN bus. Considerable reductions of the programming times are possible. However, hardware changes are required here as well.

stations; Dipl.-Ing Thomas Ströbele works as Team Leader at ZF Friedrichshafen AG and is responsible for the diagnostics and bootloader development.

: Improved utilization of the CAN bus: The maximum possible CAN bus rate should be employed for programming. With a point-to-point connection, the baud rate can be freely chosen; within the automotive CAN network and with

26

OUTLOOK

Data compression can help reducing programming times with modern ECUs significantly. This is already in use by some manufacturers, often on basis of the LZ family. However, a standard algorithm was not yet established. If extensive modifications are made (e.g. changed controller type), the data compression results should be reviewed and parameter optimizations should be

performed. Some aspects were not discussed in this article: How does data compression affect the overall tool chain and which adaptations are required? What is an adequate data format for the compressed data? Besides, the combination of data compression and encryption will gain importance. REFERENCES

[1] Lawrenz, W.: CAN Controller Area Network. Heidelberg: Hüthig, 2nd Edition, 1997 [2] Zimmermann, W., Schmidgall, R.: Bussysteme in der Fahrzeugtechnik – Protokolle und Standard, Wiesbaden: Vieweg+Teubner, 3rd Edition, 2008 [3] Salomon, D.: Data Compression; The Complete Reference, London: Springer, 1998 [4] Johannesson, R.:. Informationstheorie – Grundlage der (Tele-)Kommunikation, Luind: AddisonWesley, 1992 [5] RFC 1951 – Deflate Compressed Data Format Specification, Version 1.3, May 1996 [6] RFC 1952 – GZIP file format specification, Version 4.3, May 1996 [7] Fahrner, A., Anouz, Y., Happel, A., Geese, M., Mauer, C., Ströbele, T.: Data Compression Algorithms for EOL Flash Programming of Automotive ECUs with CAN, 10th Stuttgart International Symposium Automotive Engine Technology, Volume 1, pp 271-291, 16.-17. March 2010

IMPRINT W

O

R

L

D

W

I

D

E

www.ATZonline.com

02 | 2010 _ April 2010 _ Volume 5 Springer Automotive Media | Springer Fachmedien Wiesbaden GmbH P. O. Box 15 46 · 65173 Wiesbaden · Germany | Abraham-Lincoln-Straße 46 · 65189 Wiesbaden · Germany Amtsgericht Wiesbaden, HRB 9754, USt-IdNr. DE811148419 Managing Directors Dr. Ralf Birkelbach (Chairman), Armin Gross, Albrecht Schirmacher | Senior Advertising Armin Gross | Senior Marketing Rolf-Günther Hobbeling Senior Production Christian Staral | Sales Director Gabriel Göttlinger

SCIENTIFIC ADVISORY BOARD

Prof. Dr. Dr. h.c. Manfred Broy Technische Universität München Dipl.-Inf. Elmar Frickenstein BMW Group Ricky Hudi Audi AG Prof. Dr.-Ing. Rolf Isermann Technische Universität Darmstadt Dr.-Ing. Rainer Kallenbach Robert Bosch GmbH Prof. Dr.-Ing. Jürgen Leohold Volkswagen AG Wilfried Nietschke IAV GmbH Prof. Dr.-Ing. Konrad Reif Berufsakademie Ravensburg Prof. Dr.-Ing. Hans-Christian Reuss IVK, Universität Stuttgart Dr.-Ing. Wolfgang Runge ZF Lenksysteme GmbH Stephan Wolfsried Daimler AG

EDITOR-IN-CHARGE Wolfgang Siebenpfeiffer EDITORIAL STAFF EDITOR-IN-CHIEF Johannes Winterhagen (win) phone +49 611 7878-342 · fax +49 611 7878-462 [email protected] CHIEF-ON-DUTY Kirsten Beckmann M. A. (kb) phone +49 611 7878-343 · fax +49 611 7878-462 [email protected] SECTIONS Body, Safety Dipl.-Ing. Ulrich Knorra (kno) phone +49 611 7878-314 · fax +49 611 7878-462 [email protected] Chassis Roland Schedel (rs) phone +49 6128 85 37 58 · fax +49 6128 85 37 59 [email protected]

Electrics, Electronics Markus Schöttle (scho) phone +49 611 7878-257 · fax +49 611 7878-462 [email protected] Engine Dipl.-Ing. (FH) Moritz-York von Hohenthal (mvh) phone +49 611 7878-278 · fax +49 611 7878-462 [email protected] Heavy Duty Techniques Ruben Danisch (rd) phone +49 611 7878-393 · fax +49 611 7878-462 [email protected] Online Dipl.-Ing. (FH) Caterina Schröder (cs) phone +49 611 7878-190 · fax +49 611 7878-462 [email protected] Production, Materials Stefan Schlott (hlo) phone +49 8191 70845 · fax +49 8191 66002 [email protected] Service, Event Calendar Martina Schraad (mas) phone +49 611 7878-276 · fax +49 611 7878-462 [email protected] Transmission, Research Dipl.-Ing. Michael Reichenbach (rei) phone +49 611 7878-341 · fax +49 611 7878-462 [email protected] ENGLISH LANGUAGE CONSULTANT L Paul Willin (pw) ADDRESS P. O. Box 15 46, 65173 Wiesbaden, Germany [email protected]

ADVERTISING AD MANAGER Britta Dolch phone +49 611 7878-323 · fax +49 611 7878-140 [email protected]

YOUR HOTLINE TO ATZelektronik Editorial Staff

KEY ACCOUNT MANAGEMENT Elisabeth Maßfeller phone +49 611 7878-399 · fax +49 611 7878-140 [email protected]

 +49 611 7878-257

AD SALES MANAGER Sabine Röck phone +49 611 7878-269 · fax +49 611 7878-140 [email protected]

 +49 611 7878-179

AD SALES Jeroen Savelkoul phone +49 611 7878-179 · fax +49 611 7878-140 [email protected] DISPLAY AD MANAGER Susanne Bretschneider phone +49 611 7878-153 · fax +49 611 7878-443 [email protected] AD PRICES Price List No. 5 (10/2009) MARKETING | OFFPRINTS PRODUCT MANAGEMENT AUTOMOTIVE MEDIA Sabrina Brokopp phone +49 611 7878-192 · fax +49 611 7878-407 [email protected] OFFPRINTS Martin Leopold phone +49 2642 9075-96 · fax +49 2642 9075-97 [email protected]

Reader's Service

 +49 611 7878-151 Advertising

VDI/ÖVK/VKS members on proof of status in the form of current member certificate 94 €. Special rate for studying VDI/ÖVK/VKS members on proof of status in the form of current registration and member certificate 49 €. The subscribtion can be cancelled in written form at any time with effect from the next available issue. HINTS FOR AUTHORS All manuscripts should be sent directly to the editors. By submitting photographs and drawings the sender releases the publishers from claims by third parties. Only works not yet published in Germany or abroad can generally be accepted for publication. The manuscripts must not be offered for publication to other journals simultaneously. In accepting the manuscript the publisher acquires the right to produce royalty-free offprints. The journal and all articles and figures are protected by copyright. Any utilisation beyond the strict limits of the copyright law without permission of the publisher is illegal. This applies particularly to duplications, translations, microfilming and storage and processing in electronic systems.

PRODUCTION | LAYOUT Kerstin Brüderlin phone +49 611 7878-173 · fax +49 611 7878-464 [email protected] SUBSCRIPTIONS VVA-Zeitschriftenservice, Abt. D6 F6, ATZelektronik P. O. Box 77 77, 33310 Gütersloh, Germany Renate Vies phone +49 5241 80-1692 · fax +49 5241 80-9620 [email protected] SUBSCRIPTION CONDITIONS The eMagazine appears six times a year at an annual subscription rate of 131 €. Special rate for students on proof of status in the form of current registration certificate 61 €. Special rate for

© Springer Automotive Media | Springer Fachmedien Wiesbaden GmbH, Wiesbaden 2010 Springer Automotive Media is a brand of Springer Fachmedien. Springer Fachmedien is part of the specialist publishing group Springer Science+Business Media.