`
`Computing
`
`
`
`FOURTH EDITION
`
`Oxford New York
`
`OXFORD UNIVERSITY PRESS
`1997
`
`1
`
`SAMSUNG1057
`SAMSUNG 1057
`SAMSUNG v. SMART MOBILE
`SAMSUNGv. SMART MOBILE
`IPR2022-01004
`IPR2022-01004
`
`1
`
`
`
`Oxford University Press, Great Clarendon Street, Oxford ox2 6pp
`Oxford NewYork
`Athens Auckland Bangkok Bogota Bombay BuenosAires
`Calcutta CapeTown Dares Salaam Delhi Florence HongKong
`Istanbul Karachi Kuala Lumpur Madras Madrid Melbourne
`Mexico City Nairobi Paris Singapore Taipei Tokyo Toronto Warsaw
`and associated companies in
`Berlin Ibadan
`
`Oxford is a trade mark of Oxford University Press
`
`© Market House Books Ltd. 1983, 1986, 1990, 1996
`
`First published 1983
`Second edition 1986
`Third edition 1990
`Fourth edition 1996
`
`First issued (with corrections) as an Oxford University Press paperback 1997
`
`All rights reserved. No part of this publication may be reproduced,
`stored in a retrieval system, or transmitted, in anyform or by any means,
`without the prior permission in writing ofOxford University Press.
`Within the UK, exceptions are allowed in respect of anyfair dealingfor the
`purpose ofresearch or private study, or criticism or review, as permitted
`under the Copyright, Designs and Patents Act, 1988, or in the case of
`reprographic reproduction in accordance with the terms of thelicences
`issued by the Copyright Licensing Agency. Enquiries concerning
`reproduction outside these terms and in other countries should be
`sent to the Rights Department, Oxford University Press,
`at the address above
`
`This book is sold subject to the condition thatit shall not, by way
`oftrade or otherwise, be lent, re-sold, hired out or otherwisecirculated
`withoutthe publisher’s prior consent in anyform ofbinding or cover
`other than that in which it is published and without a similar condition
`including this condition being imposed on the subsequent purchaser
`
`British Library Cataloguing in Publication Data
`Data available
`
`Library ofCongress Cataloging in Publication Data
`Data available
`ISBN 0-19-280046-9
`
`1357910 8642
`
`Printed in Great Britain by
`Biddles Ltd
`Guildford and King’s Lynn
`
`2
`
`
`
`47
`
`plock diagram A diagram that represents
`graphically the interconnectionrelationships
`between elements of an electronic system,
`e.g. a computer system. These elements may
`range from circuits to major “functional
`units; they are described as labeled geometric
`figures. The whole block diagram mayrepre-
`sent any level ofcomputer description from a
`compound circuit
`to an overall computer
`complex.
`blocked process A “process for which a
`process description exists but whichis unable
`to proceed because it lacks some necessary
`resource. For example, a process may become
`blocked if it has inadequate memory available
`to it to allow the loading of the next part of
`the process.
`blockette Sce block.
`blocking factor The number of records,
`words, characters, orbits in a block.
`block length L Sce block (def. 1).
`2 The input word length, k, of an (n,&)
`*block code. The term is also applied to the
`codeword length, n, of an (, £) block code.
`3. The input word length (i.e. the *extension
`of the source) used in a *variable-length
`code.
`
`BNF
`
`ed scopes implicit in block structure con-
`trasts with Fortran, wherevariablesare either
`local to a program unit (subroutine) or global
`to several program units if declared to be
`COMMON.Both of these contrast with
`Cobol, where all data items are visible
`throughouttheentire program.
`Blue Book L The “coloured book that
`defines thefile transfer protocol used by the
`UK academic networking community. See
`also NIFTP.
`2 Part of the defining documentation for the
`*ISDNstandards, which further refines the
`definitions appearing in the earlier *Red
`Book.
`
`Blum’s axioms Two axioms in complexity
`theory, formulated by M. Blum. Let
`M,,M,,....M,)---
`be an effective *enumeration of the Turing
`machines andletf; be the *partial recursive
`function of a single variable that is computed
`by M,. (For technical reasonsit is simpler to
`think in terms of partial recursive functions
`than set (or language) recognizers.) If
`oF
`syuaglsen
`is a sequence a partial recursive functions
`satisfying
`axiom 1:
`f{n) is defined if and only if F{n) is
`block retrieval Fetching a block from backing
`defined,
`store as part of a *memory-management
`and axiom 2;
`process.
`F(x) Sy isa recursive predicateofi, x, and
`block-structured languagesAclass of high-
`Is
`level languages in which a program is made
`then F{n) is a computational complexity
`up ofblocks — which mayinclude nested blocks
`measure and can be thoughtof as the amount
`as components, such nesting being repeated
`of some “resource” consumed by M; in com-
`to any depth. A block consists of a sequence
`puting f(n). This notion represents a useful
`of statements and/or blocks, preceded by
`abstraction of the basic resources — time and
`declarations of variables. Variables declared
`space. Several remarkable theorems about
`at the head of a block are visible throughout
`computational complexity have been proved
`the block and any nested blocks, unlessa vari-
`for any measure of resources satisfying the
`able of the same nameis declared at the head
`two axioms (see gap theorem, speedup theo-
`ofan innerblock. In this case the new decla-
`rem).
`:
`ration is effective throughoutthe innerblock,
`BM algorithm See Boyer—Moore algorithm.
`andthe outer declaration becomes effective
`BMP Short for bitmap format. A Microsoft
`again at the end ofthe inner block. Variables
`Corp. protocol for storing raster images in an
`are said to have nested scopes.
`The conceptofblock structure was intro-
`uncompressed form.
`duced in the *Algol family of languages, and
`form,
`BNF Abbrev.
`for Backus normal
`block-structured languages are sometimes
`Backus—Naur form. The first widely used
`described as Algol-like. The conceptofnest-
`formal notation for describing the *syntax of
`
`3
`
`