Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

KEYBOARD CONTROLLER USING BINARY SEARCH SCAN MECHANISM

IP.com Disclosure Number: IPCOM000008194D
Original Publication Date: 1997-Jun-01
Included in the Prior Art Database: 2002-May-24
Document File: 3 page(s) / 163K

Publishing Venue

Motorola

Related People

lrfan Furniturewala: AUTHOR [+2]

Abstract

Keyboard controllers use linear-search scan mechanisms to detect the location of the key being pressed/released. This article proposes binary scan search algorithms for key scanning, which provide an improvement of O(N/Iog,N), N being one of the dimensions of the keyboard matrix.

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

Page 1 of 3

MO7VROLA Technical Developments

KEYBOARD CONTROLLER USING BINARY SEARCH SCAN MECHANISM

by lrfan Furniturewala and Naji Naufel

ABSTRACT

  Keyboard controllers use linear-search scan mechanisms to detect the location of the key being pressed/released. This article proposes binary scan search algorithms for key scanning, which provide an improvement of O(N/Iog,N), N being one of the dimensions of the keyboard matrix.

INTRODUCTION

  Keyboards form an integral part of any computational/communication device, providing an interface between the external user and the micro- processor/microcontroller inside the machine. The microcontrollers typically have a dedicated piece of hardware, the keyboard controller, which is used to perform all the keyboard functions. The main function of this keyboard controller is to detect which, if any, of the keys has been pressed/released, and to send the ASCII code corresponding to the key, back to the controller. The keyboard scanning should be streamlined to reduce power and improve speed. This article proposes an efficient algorithm to achieve the same. This algorithm causes the keyboard scan to be done faster and with lower power so that the scan logic can go back to sleep after the scanning has been done. This keyboard controller is a good candidate for low-power high- speed microcontroller applications.

DESCRIPTION

  Conventional keyboard controllers use a linear- search algorithm to detect the location of the key being depressed or released. Linear-search algorithms linearly explore the search-space and take O(N) time to execute, where N is the number of elements on which the search is being conducted. In case of keyboards, N would be the number of

rows or columns. The amount of power consumed by the linear-search algorithm is relatively higher than the power consumed by faster algorithms, like the binary search algorithms which take O(log,N) time to execute, since the scan logic has to be kept running for a longer time. Thus, algorithms faster than the linear search algorithms should be used, while keeping the complexity of the design to a minimum. An excellent candidate for keyboard scauuiug algorithm is the binary search algorithm, which takes on average log*N time to search through N elements.

  The following is the description of binary search algorithms on keyboard controllers. Once the signal indicating a key closure is asserted, the scan logic is enabled. It applies a binary-search mechanism by applying logic OS to half of the rows, and logic 1s to the other half. It then reads back the columns to determine which half the affected key lies in. It then applies logic OS to one half of that section, and logic 1s to the other half. It implements this algorithm recursively till only one key remains, which is the key that has been depressed/released. This algorithm executes in O(log,N) time. Thus an improvement of a factor of N/logzN is obtained by using this algorithm against the conventional linear- sea...