Browse Prior Art Database

Optimal Movement of Column Information in Bubble Lattice Files via Variable Sized Interchanges

IP.com Disclosure Number: IPCOM000087844D
Original Publication Date: 1977-Mar-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 49K

Publishing Venue

IBM

Related People

Chandra, AK: AUTHOR [+2]

Abstract

This article describes an optimal way of moving data columns in bubble lattice files, using signed-digit mixed-base number representation to obtain the interchange sequence so as to minimize the total number of steps.

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 54% of the total text.

Page 1 of 3

Optimal Movement of Column Information in Bubble Lattice Files via Variable Sized Interchanges

This article describes an optimal way of moving data columns in bubble lattice files, using signed-digit mixed-base number representation to obtain the interchange sequence so as to minimize the total number of steps.

Shown in Fig. 1, are k+1 access channels A(0)A(1)...A(k) in a bubble lattice file such that the distance between A(0)A(1) is S(i), where S(1) = 1 and S(i+1) over S(i) = b(i) > 1, b(i) integer. Let b(k) = infinity. Information under channels A(i), A(j) can be interchanged using switching techniques. By translating the whole file and utilizing the interchanges, one can effectively move the information from one column to any other column. The objective is to minimize the number of interchanges.

Suppose one wishes to move the information from one column to another at a distance d. The following procedure is optimal.

(Image Omitted)

(iii) If d = (y(k)...,y(1)), then performing y(i) of the S(i) interchanges, for i=1,2,...,k, will bring the information to a column at distance d. (Note that for y negative, the interchange is backward.)

For example, suppose there are k=3 access channels separated by distances of S(1) = 1, S(2) = 3, S(3) = 12. Thus b(1) = 3 over 1 = 3, b(2) = 12 over 3 = 4. Suppose a column has to be moved a distance of d = 10 units. 10 can be represented in the mixed base system (infinity,4,3) as (0,3,1) since 10 = 0 x 12 + 3 x 3 + 1 x 1, i.e., x(3) = 0, x(2) = 3, x(1) = 1. The column can be moved into position by x(2) = 3 moves of length S(2) = 3, and x(1) = 1 moves of length S(1) = 1, as shown in Fig. 2. Using the algorithm above, 10 can also be represented as (1,-1,1) since 10 = 1 x 12 + (-1) x 3 + 1 x 1, i.e., the column can b...