Ruby B Lee

US Patent:

6381690, Apr 30, 2002

Filed:

Aug 1, 1995

Appl. No.:

08/509867

Inventors:

Ruby B. Lee - Los Altos Hills CA

Assignee:

Hewlett-Packard Company - Palo Alto CA

International Classification:

G06F 9315

US Classification:

712223, 345522, 377 67

Abstract:

An apparatus for operating on the contents of an input register to generate the contents of an output register which contains a permutation, with or without repetitions, or a combination of the contents of the input register. The apparatus partitions the input register into a plurality of sub-words, each sub-word being characterized by a location in the input register and a length greater than one bit. In response to an instruction specifying a rearrangement of the input register, the present invention directs at least one of the sub-words in the input register to a location in the output register that differs from the location occupied by the sub-word in the input register. The ordering of the sub-words in the output register differ from the order obtainable by a single shift instruction. In the preferred embodiment of the present invention, the invention is implemented by modifying a conventional shifter comprising a plurality of layers of multiplexers. The modification comprises independently setting the control signals for at least one of the multiplexers in at least one of the layers.

US Patent:

6922472, Jul 26, 2005

Filed:

May 7, 2001

Appl. No.:

09/850237

Inventors:

Ruby B. Lee - Princeton NJ, US
Xiao Yang - Princeton NJ, US
Manish Vachharajani - Hamilton NJ, US

Assignee:

Teleputers, LLC - Princeton NJ

International Classification:

H04K001/04
H04K001/06
H04K001/00
H04K003/00

US Classification:

380 37, 380 28, 380 1

Abstract:

The present invention provides permutation instructions which can be used in software executed in a programmable processor for solving permutation problems in cryptography, multimedia and other applications. The permute instructions are based on a Benes network comprising two butterfly networks of the same size connected back-to-back. Intermediate sequences of bits are defined that an initial sequence of bits from a source register are transformed into. Each intermediate sequence of bits is used as input to a subsequent permutation instruction. Permutation instructions are determined for permitting the initial source sequence of bits into one or more intermediate sequence of bits until a desired sequence is obtained. The intermediate sequences of bits are determined by configuration bits. The permutation instructions form a permutation instruction sequence of at least one instruction.

US Patent:

6952478, Oct 4, 2005

Filed:

May 7, 2001

Appl. No.:

09/850238

Inventors:

Ruby B. Lee - Princeton NJ, US
Xiao Yang - Princeton NJ, US

Assignee:

Teleputers, LLC - Princeton NJ

International Classification:

H04K001/04
H04K001/06

US Classification:

380 37, 380 28, 380 1, 380 26

Abstract:

The present invention provides permutation instructions which can be used in software executed in a programmable processor for solving permutation problems in cryptography, multimedia and other applications. The permute instructions are based on an omega-flip network comprising at least two stages in which each stage can perform the function of either an omega network stage or a flip network stage. Intermediate sequences of bits are defined that an initial sequence of bits from a source register are transformed into. Each intermediate sequence of bits is used as input to a subsequent permutation instruction. Permutation instructions are determined for permuting the initial source sequence of bits into one or more intermediate sequence of bits until a desired sequence is obtained. The intermediate sequences of bits are determined by configuration bits. The permutation instructions form a permutation instruction sequence, of at least one instruction.

US Patent:

7092526, Aug 15, 2006

Filed:

May 7, 2001

Appl. No.:

09/850380

Inventors:

Ruby B. Lee - Princeton NJ, US

Assignee:

Teleputers, LLC - Princeton NJ

International Classification:

H04K 1/04
G06F 7/32
G06F 15/00

US Classification:

380 37, 708520, 712 10

Abstract:

The method and system provides a set of permutation primitives for current and future 2-D multimedia programs which are based on decomposing images and objects into atomic units, then finding the permutations desired for the atomic units. The subword permutation instructions for these 2-D building blocks are also defined for larger subword sizes at successively higher hierarchical levels. The atomic unit can be a 2×2 matrix and four triangles contained within the 2×2 matrix. Each of the elements in the matrix can represent a subword of one or more bits. The permutations provide vertical, horizontal, diagonal, rotational, and other rearrangements of the elements in the atomic unit.

US Patent:

7174014, Feb 6, 2007

Filed:

May 7, 2001

Appl. No.:

09/850239

Inventors:

Ruby B. Lee - Princeton NJ, US
Zhijie Shi - Princeton NJ, US

Assignee:

Teleputers, LLC - Princeton NJ

International Classification:

H04K 1/00

US Classification:

380 28, 380 44, 380265, 377 54, 377 60, 377 67, 377 81, 34082568, 365 78, 711109, 712 1, 712 10, 712 24, 712223

Abstract:

The present invention provides permutation instructions usable in a programmable processor for solving permutation problems in cryptography, multimedia and other applications. PPERM and PPERMR instructions are defined to perform permutations by a sequence of instructions with each sequence specifying the position in the source for each bit in the destination. In the PPERM instruction bits in the destination register that change are updated and bits in the destination register that do not change are set to zero. In the PPERMR instruction bits in the destination register that change are updated and bits in the destination register that do not change are copied from intermediate result of previous PPERMR instructions. Both PPERM and PPERMR instructions can individually do permutation with bit repetition. Both PPERM and PPERMR instructions can individually do permutation of bits stored in more than one register.

US Patent:

7274825, Sep 25, 2007

Filed:

Mar 31, 2003

Appl. No.:

10/403754

Inventors:

Ruby B. Lee - Princeton NJ, US
Dale Morris - Steamboaat Springs CO, US

Assignee:

Hewlett-Packard Development Company, L.P. - Houston TX

International Classification:

G06K 9/36

US Classification:

382239, 382236

Abstract:

A block-matching method reduces pixel depth prior to match evaluation to drastically reduce the computations required intensive block-matching applications such motion estimation for video compression. Pixel-depth reduction is achieved by analyzing incorporating images to determine how to reduce pixel depth so as to retain information useful for block matching. Original pixel values (e. g. , 8-bit), are compressed to lower-depth (e. g. , e. g. , 1-bit or 1. 6-bit) pixel values. The resulting converted blocks are XORed to yield a comparison image. The 1s in the comparison image are tallied to provide a match measure. In the image analysis, the original images can be subsampled and averages can be computed based on the subsample pixels to reduce computational overhead.

US Patent:

7424597, Sep 9, 2008

Filed:

Mar 31, 2003

Appl. No.:

10/403785

Inventors:

Ruby B. Lee - Princeton NJ, US
Dale Morris - Steamboaat Springs CO, US

Assignee:

Hewlett-Packard Development Company, L.P. - Houston TX

International Classification:

G06F 9/312
G06F 9/315

US Classification:

712210, 712227, 712228

Abstract:

Parallel table lookups are implemented using variable Mux instructions to reorder data. Table data can be represented in a “table” register, while the desired ordering can be represented in an “Index” register. A direct variable Mux instruction can specify the table register and the index register as arguments, along with a result register. The instruction writes at least some of the data from the table register into the result register as specified in the index register. If the entire table cannot fit within a single register, entries can be divided between two or more table registers. An indirect variable Mux instruction can specify both a table-register-select register and a subword-location-select register. Both the direct and indirect Mux instructions can be used with entry data that is divided in accordance with significance between registers. In that case, plural Mux instructions are used with UnPack instructions that concatenate portions of the table entries.

US Patent:

7519795, Apr 14, 2009

Filed:

Feb 16, 2005

Appl. No.:

11/058819

Inventors:

Ruby B. Lee - Princeton NJ, US
Zhijie Shi - Princeton NJ, US

Assignee:

Teleputers, LLC - Princeton NJ

International Classification:

G06F 9/30

US Classification:

712223

Abstract:

The present invention provides permutation instructions which can be used in software executed in a programmable processor for solving permutation problems in cryptography, multimedia and other applications. PPERM and PPERM3R instructions are defined to perform permutations by a sequence of instructions with each sequence specifying the position in the source for each bit in the destination. In the PPERM instruction bits in the destination register that change are updated and bits in the destination register that do not change are set to zero. In the PPERM3R instruction bits in the destination register that change are updated and bits in the destination register that do not change are copied from intermediate result of previous PPERM3R instructions. Both PPERM and PPERM3R instruction can individually do permutation with bit repetition. Both PPERM and PPERM3R instruction can individually do permutation of bits stored in more than one register.