Cyclic redundancy data check encoding method and apparatus

• US 4,283,787 A
• Filed: 08/06/1979
• Issued: 08/11/1981
• Est. Priority Date: 11/06/1978
• Status: Expired due to Term

• Current Assignee: British Broadcasting Corporation
• Original Assignee: British Broadcasting Corporation
• Inventors: Chambers, John P.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US06/064,188
• Time in Patent Office: 736 Days
• Field of Search: 371/38, 371/37
• US Class Current: 714/781
• CPC Class Codes: H03M 13/091 Parallel or block-wise CRC computation
• CPC Class Codes: H04N 7/0357 for error detection or correction

Abstract

A cyclic redundancy check word is customarily placed at the end of a data block, occupying one or more of the last bytes of the block. This can impose an undesirable restraint upon the person composing the data block, e.g. the editor of a teletext page. The invention allows the check word effectively to be embedded anywhere convenient in the block. A location in the block is selected (one or more bytes--preset address 16) and all preceding bytes are cyclically encoded (encoder 18) to yield a first check word. The succeeding bytes are subjected in reverse order to complementary encoding (encoder 28) to yield a second check word. A third check word is formed from the first and second check words (encoding logic 32) and inserted in the selected location. Each bit of the third word is the logical product of the corresponding bit of the first word and selected bits of the second word, such that when the bytes of the complete block, including the third word, are cyclically encoded, the final check word has the required final form, e.g. all zeroes, to indicate compliance of the block with the cyclic redundancy check. The location can be selected by the editor but is preferably selected automatically by a search for a free location complying with predetermined conditions.

Claims

1. Cyclic redundancy check data encoding apparatus comprising

a multi-word memory for storing a block of data,

input means for entering a block of data into the memory, addressing means operative to provide an address designating a selected part of the stored block in the memory,

an encoder,

means for reading words from the memory to the encoder for encoding the words preceding the said selected part designated by the addressing means, the encoder including a register and being constructed to provide a first check word in the register of the encoder,

a complementary encoder,

means for reading words from the memory to the complementary encoder for encoding, in reverse order, the words succeeding the said selected part designated by the addressing means, the complementary encoder including a register and being constructed to provide a second check word in the register of the complementary encoder,

encoding logic responsive to the first and second check words in the registers to generate a third check word, and means responsive to the encoding logic and the addressing means for entering the third check word in the memory to occupy the selected part of the block of data designated by the addressing means.

2. A method of processing a multi-word block of data to render the block consistent with a given cyclic redundancy check, comprising the steps of

cyclically encoding the words preceding a predetermined part of the block to generate a first check word,

cyclically encoding the words succeeding the said part of the block in reverse order and with complementary encoding to generate a second check word,

generating a third check word from the first and second check words, and

introducing the third check word into the said part of the block, and wherein the step of generating the third word comprises forming the bits of the third word in accordance with predetermined logical functions of bits of the first and second words such that when the whole block, including the introduced third word, is cyclically encoded, the final check word thereby generated has a predetermined form.

3. A method according to claim 2, and further including the step of

automatically scanning the block to select a free location for the introduced check word, thereby predetermining the said part of the block.