US 5,710,561 AGranted

Method and apparatus for double run-length encoding of binary data

AssigneePeerless Systems Corporation

InventorsKen Schmidt, Jeff Horowitz

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method and apparatus for losslessly compressing binary data using a technique referred to as Double Run-Length Encoding (DRLE). DRLE has particular application to the compression of gray-scale data as it is being processed for printing by a laser printer or other continuous raster scan device. DRLE records repeating patterns of ones and zeros with little computational complexity. Compression ratios that may be an order of magnitude or more are obtained frequently on data that may not compress well using traditional Run-Length Encoding (RLE). DRLE uses a sequential history of order-pairs that denote variable-length patterns of zeros and ones, and then encodes these patterns as they repeat themselves.

Claims12

Dependent claims

A system for performing lossless compression of binary data comprising:

a) means for run length encoding a stream of binary data as encoded pairs, each encoded pair representing a run of 0's and a run of 1's;
b) means for storing a history of said encoded pairs;
c) means for comparing a current encoded pair with at least first and second prior encoded pairs from said history;
d) means for
i) selecting one of:
1) said current encoded pair to which has been added a first prepended code, and
2) one of:
a first code indicating that said current encoded pair matched said second prior encoded pair and did not match said first prior encoded pair, and
a second code indicating that said current encoded pair matched said second prior encoded pair and said first prior encoded pair, said first and second codes having added thereto a second prepended code, and
ii) generating as an output said selected one, and a length of said selected one;
e) means for packing said output into words having a predetermined length.

8 more elements

A method for performing lossless compression of binary data comprising the steps of:

a) run length encoding a stream of binary data as encoded pairs, each encoded pair representing a run of 0's and a run of 1's;
b) storing a history of said encoded pairs;
c) comparing a current encoded pair with at least first and second prior encoded pairs from said history;
d) selecting one of:
1) said current encoded pair to which has been added a first prepended code, and
2) one of:
a first code indicating that said current encoded pair matched said second prior encoded pair and did not match said first prior encoded pair, and
a second code indicating that said current encoded pair matched said second prior encoded pair and said first prior encoded pair, said first and second codes having added thereto a second prepended code, and
e) generating as an output said selected one and a length of said selected one;
and
f) packing said output into words having a predetermined length.

8 more elements

Dependencies are inferred from the claim text.

Facts

Application: 08/582,150Filed 2 Jan 1996
Granted: 20 Jan 1998
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06T 9/005
Image coding: statistical coding, e.g. Huffman, run length coding
H03M 7/3084
Compression ; Expansion; Suppression of unnecessary data, e.g. redundancy reduction: using adaptive string matching, e.g. the Lempel-Ziv method
H03M 7/46
Compression ; Expansion; Suppression of unnecessary data, e.g. redundancy reduction: conversion to or from run-length codes, i.e. by representing…
H04N 1/4105
Bandwidth or redundancy reduction: for halftone screened pictures

Family

No related US applications are recorded in the indexed filing history.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key