Novel Error Detection Algorithm for LZSS Compressed Data

Abstract

Conventional error detection schemes, such as the repetition code, parity bit, and Hamming code, have been used to detect bit errors in data. These conventional schemes require the insertion of additional bits to detect bit errors, but the code rate decreases in proportion to the number of additional bits. In order to avoid this problem, in this paper, we introduce three special bit patterns in Lempel-Ziv-Storer-Szymanski (LZSS) compressed data. In addition, based on the three bit patterns, we propose a novel error detection algorithm for LZSS compressed data, which does not need to use additional bits to detect bit errors. In the simulation, it is demonstrated that the compression ratio and running time of the proposed algorithm are better than those of the conventional schemes, such as repetition code, parity bit, and Hamming code. In addition, it is shown that when more than/equal to seven bit errors occur, the proposed algorithm nearly always detects the presence of errors in the LZSS compressed data.

Keywords

• Error detection
• Lempel-Ziv-Storer-Szymanski (LZSS)
• lossless data compression