• DocumentCode
    958523
  • Title

    Signed digit representations of minimal Hamming weight

  • Author

    Arno, Steven ; Wheeler, Ferrell S.

  • Author_Institution
    Supercomput. Res. Center, Bowie, MD, USA
  • Volume
    42
  • Issue
    8
  • fYear
    1993
  • fDate
    8/1/1993 12:00:00 AM
  • Firstpage
    1007
  • Lastpage
    1010
  • Abstract
    The authors give an online algorithm for computing a canonical signed digit representation of minimal Hamming weight for any integer n. Using combinatorial techniques, the probability distributions Pr[Kr=h], where Kr is taken to be a random variable on the uniform probability space of k-digit integers is computed. Also, using a Markov chain analysis, it is shown that E(Kr)~(r-1)k /(r+1) as k→∞
  • Keywords
    digital arithmetic; Markov chain analysis; combinatorial techniques; k-digit integers; minimal Hamming weight; online algorithm; probability distributions; random variable; signed digit representations; uniform probability space; Digital arithmetic; Distributed computing; Greedy algorithms; Hamming weight; Probability distribution; Random variables;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/12.238495
  • Filename
    238495
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=958523