Browse Prior Art Database

A CYCLIC CHECK COMPUTER FOR ERROR DETECTION

IP.com Disclosure Number: IPCOM000128385D
Original Publication Date: 1968-Jun-01
Included in the Prior Art Database: 2005-Sep-15
Document File: 15 page(s) / 53K

Publishing Venue

Software Patent Institute

Related People

Burkhalter, Kenneth E.: AUTHOR [+3]

Abstract

This report discusses the design and use of a hardware device to compute from an input message stream a residue, modulo a program-selectable polynomial, which serves as an error detecting check over the message itself. The purpose of this device is to free the support processor (the Data Concentrator PDP-8 in this case) from the software overhead burden of checksum computation, which may require up to 500 microseconds per input character in the case of the PDP-8. It is readily possible to compute the same checksum by hardware methods in 4 microseconds! In addition, the reduced time required allows the computation to be accomplished in real time rather than task time, thus allowing simpler programming conventions. The cyclic check generator is composed of two registers which are loaded and read under program control. The character register is loaded with the new input character and the residue register is loaded with the last computed residue (zero for the first time through). After executing the start command the processor then reads the new contents of the residue register to obtain the current check digits. Since the cyclic check interface holds the PDP-8 in PAUSE state until checksum computation is completed, the programmer is always guaranteed to have the current results available when the residue register is read after initiating computation. The generator is capable of operating in three different modes to compute the residue on 6, 8, or bit wide characters, following IBM binary synchronous communication conventions. This report will serve as a progress report for those interested in project technical progress, and as a maintenance manual for those responsible for future system maintenance. Basic design discussions and objectives will be described first, followed by a brief overall equipment description with detailed logic explanations and programming considerations. Finally, maintenance software is included to aid in hardware debugging.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A CYCLIC CHECK COMPUTER FOR ERROR DETECTION

THE UNIVERSITY OF MICHIGAN Memorandum 19 Kenneth E. Burkhalter

CONCOMP: Research in Conversational Use of Computers F.H. Westervelt, Project Director ORA Project 07449

supported by: ADVANCED RESEARCH PROJECTS AGENCY DEPARTMENT OF DEFENSE WASHINGTON, D.C.

CONTRACT NO. DA-49-083 OSA-3050 ARPA ORDER NO. 716

administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR June 1968

TABLE OF CONTENTS

LIST OF FIGURES.....v
I. INTRODUCTION.....1
II. DESIGN DISCUSSION.....2
a. Error Checking.....2
b. Design Objectives.....4
III. SYSTEM DESCRIPTION.....5
IV. PROGRAMMING AND CONTROL CONSIDERATIONS.....10
V. DETAILED LOGIC DISCUSSIONS.....12
IOP Decoding and Device Selection.....12
Character Buffer.....17
Residue Register Control.....19
Residue Register Mod 2 Adders.....23
Residue Register.....26
Shift Control and Mode Storage.....26
PDP-8 Added Circuitry.....30
APPENDIX A. UTILIZATION MODULE LIST AND CIRCUIT NAME MAP.....A-1
APPENDIX B. CONNECTOR MAPS.....B-1
APPENDIX C. DIAGNOSTIC PROCEDURES.....C-1

LIST OF FIGURES

University of Michigan Page 1 Jun 01, 1968

Page 2 of 15

A CYCLIC CHECK COMPUTER FOR ERROR DETECTION

Figure

1 General Block Diagram.....6
1.1 GRC-16 BCC Generation.....
1.2 CRC-12 BCC Generation.....8
2 Cyclic Check Computer-Example Routines.....13
3 IOP Address Decode AC Buffers.....14
4 Character Register.....18
5 Residue Register Control.....20
6 IN/OUT Gating Residue Register.....22
7 MOD 2 Adders.....24
8 Generator Shift Register.....27
9 Run and Mode Control.....28
10 Additions to PDP-8 CPU.....31
B1 Cable Layout Map.....B-2
B2 Connector Map.....B-3
B3 Connector Map.....B-4
B4 Connector Map.....B-5

[ Chapter 1 ] I. INTRODUCTION

This report discusses the design and use of a hardware device to compute from an input message stream a residue, modulo a program-selectable polynomial, which serves as an error detecting check over the message itself. The purpose of this device is to free the support processor (the Data Concentrator PDP-8 in this case) from the software overhead burden of checksum computation, which may require up to 500 microseconds per input character in the case of the PDP-8. It is readily possible to compute the same checksum by hardware methods in 4 microseconds! In addition, the reduced time required allows the computation to be accomplished in real time rather than task time, thus allowing simpler programming conventions.

The cyclic check generator is composed of two registers which are loaded and read under program control. The character register is loaded with the new input character and the residue register is loaded with the last computed residue (zero for the first time through). After executing the start command the processor then reads the new contents of the residue register to obtain the current check digits. Since the cyclic check interface holds the PDP-8 in PAUSE state until checksum compu...