Dismiss
InnovationQ/InnovationQ Plus content will be updated on Sunday, June 25, 10am ET, with new patent and non-patent literature collections. Click here to learn more.
Browse Prior Art Database

RELIABLE CHECKSUMS

IP.com Disclosure Number: IPCOM000008291D
Original Publication Date: 1997-Sep-01
Included in the Prior Art Database: 2002-Jun-04
Document File: 5 page(s) / 205K

Publishing Venue

Motorola

Related People

Bill Hanks: AUTHOR [+3]

Abstract

Digital communication systems such as digital radio and cellular communication systems, and high speed modems such as CyberSurferTM, generally, perform data communication over an unreliable physical medium and therefore, must perform data validation. Traditional methods use checksums which are vulnerable to swap errors to detect transmission errors. This paper describes a highly reliable, low overhead method of detecting trans- mission errors by utilizing multiple overlapping checksums.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 35% of the total text.

Page 1 of 5

0 M

MOTOROLA Technical Developments

RELIABLE CHECKSUMS

by Bill Hanks, Alan Grau and Tim Gronkowski

INTRODUCTION

  Digital communication systems such as digital radio and cellular communication systems, and high speed modems such as CyberSurferTM, generally, perform data communication over an unreliable physical medium and therefore, must perform data validation. Traditional methods use checksums which are vulnerable to swap errors to detect transmission errors. This paper describes a highly reliable, low overhead method of detecting trans- mission errors by utilizing multiple overlapping checksums.

BACKGROUND

  The inherent nature of the physical mediums utilized in data communication results in the corruption of some of the data being transmitted,

therefore, data transmission is not completely reliable. Checksum and error correction methods were devised to overcome these problems. Figure 1 shows the steps involved in validation of transmitted data using a checksum. Error detection methods are similar. The sender computes the checksum (CS) on the message (data to be transmitted) to produce the transmitted checksum value (TCS). The sender then transmits both both the message and the TCS. When the transmitted data is received, the receiver will compute the checksum on the trans- mitted message, using the same checksum calcula- tion process, to produce the computed checksum value (CCS). The CCS value is then compared to the TCS value. If the values are the same the data transmission is assumed to have completed without error. If the checksum values are different then there was an error in the transmission and the data must be retransmitted.

Sender Processing

Y

fl

Message 1
I. Compute. the Checksum on Message

2. Concatenate Message and TCS

3. Transmit Message + TCS

Potential Cormption of Transmitted Message

1

'I

( TCS ( Message

\ /

Receiver Processing

TCS Message I
1. Compute the Checksum on the Message
2. Compare the Computed and Transmitted C

pJ:pJ

3. If TCS = CCS. transmission succeeded

4. If TCS I= CCS, retransmit the message

L.

S

i

Fig. 1 Validation of Transmitted Data Using Checksums

0 Molorok 1°C. ,997

88 September 1997

[This page contains 15 pictures or other non-text objects]

Page 2 of 5

Technical Developments

SOLUTION

  A standard checksum is calculated simply by manner will not detect "swap errors" where two adding the value of all the bytes to be transmitted. elements in the message are swapped, or other For example, the checksum of the message errors which result in the same checksum value being computed.

32 12 02 47 98 61

is 249. Standard checksums computed in this

Checksum 13

swa error

A

Receiver w 7,2,3,1,13

This Message is in error. butthe-umwillrmt
detect the error.

Sender

1,2,3,7, 13


non- swap error

it ) Receiver

1,4,3,7,~ 13 This Message is in error, and the checksum will detect the,error.

Fig. 2 Checksnms witi: Swap ~FAXOFS

  This method utilizes n overlapping checksums, each of different length, .to perform data validati...